Dijkstra's algorithm takes significant computational time. The time complexity in a general case is O(V2), where V is the number of vertices. This is improved to O(E log V) (where E is the number of edges) if the graph representation is changed to adjacency lists. While a polynomial time complexity such as O(V2) would seem high, it is better than brute force algorithms which provide much higher computational times.
You can find the full working implementation here:
xxxxxxxxxx90
dijkstra(graph, "a", "f");const graph = { a: { b: 5, c: 2 }, b: { a: 5, c: 7, d: 8 }, c: { a: 2, b: 7, d: 4, e: 8 }, d: { b: 8, c: 4, e: 6, f: 4 }, e: { c: 8, d: 6, f: 3 }, f: { e: 3, d: 4 },};​const printTable = (table) => { return Object.keys(table) .map((vertex) => { var { vertex: from, cost } = table[vertex]; return `${vertex}: ${cost} via ${from}`; }) .join("\n");};​const tracePath = (table, start, end) => { var path = []; var next = end; while (true) { path.unshift(next); if (next === start) { break; } next = table[next].vertex; }​OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
