Dijkstra's Shortest Path

BFS from the last chapter guarantees the shortest path in an unweighted graph by exploring in order of hop count. The moment edges carry different weights - a road that takes 10 minutes vs. one that takes 1 minute - hop count stops being the right thing to minimize, and BFS quietly gives wrong answers without any obvious sign that anything broke.

Consider a weighted, directed graph: A -> B costs 4, A -> C costs 1, C -> B costs 2, B -> D costs 1, and C -> D costs 5. BFS, treating every edge as costing the same "1 hop," would report A to B as distance 1 (direct edge) and never consider that going A -> C -> B costs 1 + 2 = 3, which is cheaper than the direct edge's cost of 4 despite being two hops instead of one. Minimizing hop count and minimizing total weight are simply different problems once weights vary, and BFS only solves the former.

Dijkstra's algorithm fixes this with one change in strategy: instead of a plain queue, use a min-heap keyed by total distance-so-far, and always pop and finalize whichever node currently has the smallest known distance from the start. Every time a node is popped, relax its outgoing edges - if reaching a neighbor through this node would be cheaper than the neighbor's current known distance, update it and push the improved distance onto the heap. Because the heap always surfaces the globally cheapest unfinalized node next, once a node is popped, its distance is guaranteed final - no future edge relaxation can ever find something cheaper, since every other node still in the heap already costs at least as much.

Using the graph from above (A -> B: 4, A -> C: 1, C -> B: 2, B -> D: 1, C -> D: 5), starting from A: the heap begins with (0, A). Popping A relaxes B to 4 and C to 1, pushing (4, B) and (1, C). Popping (1, C) (the smallest in the heap) relaxes B down to 1 + 2 = 3 (better than 4, so update and push (3, B)) and D to 1 + 5 = 6 (push (6, D)). Popping (3, B) relaxes D to 3 + 1 = 4 (better than 6, so update and push (4, D)). Next the heap yields (4, B) - but distances[B] is already 3, so 4 > 3 means this is a stale entry, skipped without doing any work. Then (4, D) is popped and finalized (D has no outgoing edges to relax). Finally (6, D) surfaces as stale too (4 < 6) and is skipped. Final shortest distances from A: A=0, B=3, C=1, D=4 - correctly finding the A -> C -> B -> D route as cheaper than the more "direct-looking" A -> B -> D, exactly the kind of answer BFS could never have produced.

• -The min-heap replaces BFS's plain queue - it reorders work by cost-so-far instead of discovery order, which is the only change needed to handle weighted edges correctly.
• -A node's distance is only truly final once it is popped from the heap - until then, a cheaper path might still be found.
• -The heap can hold multiple stale entries for the same node; the `if current_dist > distances[node]: continue` check is what safely skips them without corrupting the result.
• -Dijkstra requires non-negative edge weights - a negative edge could make a "finalized" node's distance improve later, breaking the core guarantee the algorithm relies on.