Dijkstra's algorithm in JavaScript

Question

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 < arr.length; ++i) {
      let node = arr[i];

      if (node.x < maxWidth) {
        next.push({
          x: node.x + 1,
          y: node.y,
          weight: node.weight + grid[node.y][node.x + 1]
        });
      }

      if (node.y < maxHeight) {
        next.push({
          x: node.x,
          y: node.y + 1,
          weight: node.weight + grid[node.y + 1][node.x]
        });
      }
    }
  } while (next.length);

  return Math.min(...arr.map(o => 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, however, my solution is timing out all the time (12s+).

The first big test passes the position 29,29 (see grid here)

I wonder if I'm implementing it right. Is there something wrong? Is there a way to improve performance so it can work for really big maps?

Answer 1

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.

Answer 2

Before it would search all possible paths equally, and this was using more memory than any machine would be able to handle.

So I improved a bit by searching smaller paths first and stopping when I reach the end.

function minPath(grid, x, y) {
  var next = [{ x: 0, y: 0, weight: grid[0][0], steps: 0 }];
  var arr = next;

  var found;

  do {
    arr = next;
    next = [];

    for (var i = 0; i < 1 && arr.length; ++i) {
      var node = arr[i];

      if (node.x === x && node.y === y) {
        found = node;
        break;
      }

      if (node.x < x) {
        next.push({
          x: node.x + 1,
          y: node.y,
          weight: node.weight + grid[node.y][node.x + 1],
          steps: node.steps + 1,
        });
      }

      if (node.y < y) {
        next.push({
          x: node.x,
          y: node.y + 1,
          weight: node.weight + grid[node.y + 1][node.x],
          steps: node.steps + 1,
        });
      }
    }

    if (!found) {
      next = next.concat(arr.slice(1));
      next = next
        .sort((a, b) => b.steps - a.steps)
        .sort((a, b) => a.weight - b.weight);
    }
  } while (next.length && !found);

  return found.weight;
}

This is better, but not even close to be acceptable. I'm running this code for several minutes now and it still didn't finish.