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:
xxxxxxxxxx
90
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;
}
​