Dijkstra's Shortest Distances
graph maps each node to an object of { neighbour: weight } with non-negative weights. Return an object mapping every node to its shortest distance from source, with null for nodes that cannot be reached.
dijkstra({ A: { B: 1, C: 4, D: 7 }, B: { C: 2, E: 5 }, C: { D: 1 }, D: { E: 3 }, E: {} }, "A")
-> { A: 0, B: 1, C: 3, D: 4, E: 6 }Hints
Hint 1
Start with distance 0 at the source and infinity elsewhere. Repeatedly take the unfinished node with the smallest distance and relax its edges.
Hint 2
A binary heap makes the pick O(log n); with a stale-entry check (skip a popped entry whose distance is larger than the recorded one) you never need decrease-key.