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?