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.