-
AlgorithmsLogic
Description Based on the pseudocode at: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Please check the test cases for an example input.
Code function dijkstra(numberOfVertices, edges, source, target) { if (target >= numberOfVertices) throw new Error('target outside available vertices'); if (source < 0 || numberOfVertices === 0) throw new Error('source outside available vertices'); const dist = {}; const prev = {}; const q = []; for (let v = 0; v < numberOfVertices; v++) { dist[v] = Infinity; prev[v] = null; q.push(v); } dist[source] = 0; while (q.length) { // Node with the least distance will be selected first const u = q.reduce((minV, v) => dist[v] < dist[minV] ? v : minV ); if (u === target) break; // Remove u from q q.splice(q.indexOf(u), 1); (edges[u] || []) .forEach(edge => { const alt = dist[u] + edge.cost; if (alt < dist[edge.to]) { dist[edge.to] = alt; prev[edge.to] = u; } }); } if (dist[target] === Infinity) return null; const s = []; let u = target; while (prev[u] !== null) { s.unshift(u); u = prev[u]; } s.unshift(u); return s; }
Test Cases const numberOfVertices = 5; // 0, 1, 2, 3, 4 const edges = { 0: [{ to: 1, cost: 2}], 1: [{ to: 0, cost: 1}, { to: 2, cost: 3}, { to: 3, cost: 10}], 3: [{ to: 4, cost: 2}]}; const start = 0; const finish = 4; describe("Examples", function() { it("should return the best path", function() { const path = dijkstra(numberOfVertices, edges, start, finish); console.log(path); Test.assertSimilar(path, [0, 1, 3, 4], "Returns the correct path"); }); it("should return null when no path is possible", function() { const path = dijkstra(numberOfVertices + 1, edges, start, finish + 1); console.log(path); Test.assertEquals(path, null, "Returns null"); }); it("should throw an error if target is outside the available vertices", function() { Test.expectError(() => dijkstra(numberOfVertices, edges, start, finish + 1)); }); it("should throw an error if source is outside the available vertices", function() { Test.expectError(() => dijkstra(numberOfVertices, edges, start - 1, finish)); Test.expectError(() => dijkstra(0, edges, 0, 0)); }); });
Output:
-
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
Please sign in or sign up to leave a comment.