Dijkstra's algorithm in JavaScript

I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars.

In this scenario there is a map:

[
  [1,2,3],
  [4,8,2],
  [1,5,3],
]

We start at the position 0, 0 and we can only move right or down. Our goal is to reach the position x, y passed to the function and get the sum of the shortest path. In this case the result would be 1+2+3+2+3 = 11 (for x and y pointing to the end of the square.

I implemented this code as an attempt to solve the challenge, but it times out. (It is safe to run, the part that timeout is commented).



const minPath = (grid, x, y) => {
const maxWidth = x;
const maxHeight = y;

let next = [{ x: 0, y: 0, weight: grid[0][0] }];
let arr = next;

do {
arr = next;
next = [];

for (let i = 0; i o.weight));
};

const smallSquare = [
[1,2,3],
[4,8,2],
[1,5,3],
];

console.time('small');
console.log(minPath(smallSquare, smallSquare.length - 1, smallSquare.length - 1));
console.timeEnd('small');

// just an example, values can be generated at random
const bigSquare = [[29,24,84,67,8,9,52,47,68,58,33,58,69,80,26],[95,98,94,47,20,70,46,87,80,82,96,28,4,52,10],[9,70,31,22,87,71,46,33,79,28,26,56,26,7,73],[35,2,88,70,20,41,39,85,35,35,19,1,41,85,63],[59,87,27,33,60,65,12,5,17,60,10,26,11,10,8],[6,15,49,32,54,39,93,28,32,32,51,52,13,92,44],[6,58,26,88,78,73,71,60,77,20,49,43,35,27,38],[59,73,86,52,27,85,74,67,85,72,92,55,31,76,43],[25,60,14,92,49,23,51,93,8,21,94,35,63,33,33],[34,33,18,99,67,38,36,80,5,6,82,87,33,97,3],[54,88,53,82,31,36,69,83,73,92,89,0,19,48,12],[6,89,54,88,35,13,1,33,38,31,59,93,29,72,55],[3,94,94,6,41,19,19,4,31,71,0,64,76,12,85],[96,20,58,69,65,79,40,25,58,52,79,17,97,32,42],[12,86,40,49,63,98,65,8,14,90,15,8,53,57,65]];

// This will break the page if run here
// console.time('bigSquare');
// console.log(minPath(bigSquare, bigSquare.length - 1, bigSquare.length - 1));
// console.timeEnd('bigSquare');



It seems to work pretty well, ho

It would help if you format your solution so that it can be copy and pasted into demonstrable code and if you provide a case where it times out.

In general if you're trying to find the shortest path (for example in a GPS) you would prune paths as you go, i.e. if you are trying to find the shortest route from A to E, you might calculate A-B-D and A-C-D, if A-B-D is shorter then you would prune A-B-D from the set of paths under consideration and not bother to calculate A-C-D-E.

That said I would just iterate through each cell calculating the cheapest way there (either from above or the left):

const minPath = (grid, x, y) => {

  function makeArray(width, height) {
    let outputArray = new Array(height);
    let row         = new Array(width);
    for(let iy = 0; iy < height; iy++) {
        outputArray[iy] = row.slice();
    }
    return outputArray;
  }

  function initArrayBorders(outputArray, grid, width, height)  {
    outputArray[0][0] = grid[0][0];
    for (let ix = 1; ix < width; ix++) {
      outputArray[ix][0] = outputArray[ix-1][0] + grid[ix][0];
    }  
    for (let iy = 1; iy < height; iy++) {
      outputArray[0][iy] = outputArray[0][iy-1] + grid[0][iy];
    }  
  }

  function fillArray(outputArray, grid, width, height) {
    for (let ix = 1; ix < width; ix++) {
      for (let iy = 1; iy < height; iy++) {
        let minWeight = Math.min(outputArray[ix-1][iy], 
                                 outputArray[ix][iy-1]);
        outputArray[ix][iy] = minWeight + grid[ix][iy];
      }
    }
  }

  let width = x + 1, height = y + 1;
  let outputArray = makeArray(width, height);
  initArrayBorders(outputArray, grid, width, height);
  fillArray(outputArray, grid, width, height)
  console.table(outputArray);

  return outputArray[x, y];
};

console.clear();
console.log( minPath( [
  [1,2,3],
  [4,8,2],
  [1,5,3],
], 2, 2) );

I'm sure Google would also provide some other solutions.

StackExchange Code Review Q#156059, answer score: 3