3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Without having looked too closely at your solution, if it takes too long consider how to avoid doing unnecessary work. Consider that you may know early on that some paths are not worth exploring. \$\endgroup\$ – user650881 Feb 23 '17 at 4:20
  • \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Feb 23 '17 at 22:48
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.