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.

Bellman-Ford answers the same single-source shortest-path question as Dijkstra, but with a completely different strategy: instead of greedily expanding the cheapest known node first, it simply relaxes every edge in the graph, n - 1 times over, where n is the number of nodes. That repetition is not arbitrary. In a graph with no negative-weight cycle, any shortest path visits at most n - 1 edges, so n - 1 full passes over every edge are guaranteed to have propagated the correct distance to every node, no matter what order the edges happen to be processed in. Because it never relies on "once finalized, always final" the way Dijkstra does, it works correctly even when some edges are negative.

The extra nth pass at the end is what Dijkstra has no equivalent of: if any edge can still be relaxed after n - 1 full passes have already run, that means distances are still improving after every legitimate shortest path should have already stabilized, which can only happen if a negative-weight cycle reachable from the start is letting some "distance" shrink forever. Returning None in that case is the correct, meaningful answer. No well-defined shortest path exists once a negative cycle can be looped indefinitely to keep lowering the total cost.

Both Dijkstra and Bellman-Ford answer a single-source question: shortest distances from one starting node to everywhere else. Floyd-Warshall answers a different question entirely: the shortest distance between every pair of nodes, all at once, in one computation. It is a dynamic programming algorithm, not a traversal: dp[i][j], after considering intermediate node k, holds the shortest known distance from i to j using only nodes 0 through k as allowed stopping points along the way. Allowing one more intermediate node, k, to enter the mix can only help if routing through it is cheaper than not, which is exactly the update rule.

The triple-nested loop gives Floyd-Warshall an O(n³) time complexity and O(n²) space for the distance grid, noticeably more expensive than a single Dijkstra run, but that cost buys every pair's shortest distance at once. Running Dijkstra from every node individually to get the same all-pairs answer costs roughly O(n · (n + e) log n) instead, which for a dense graph (e close to n²) can actually be slower than Floyd-Warshall's flat O(n³), on top of being considerably more code to write and get right. Floyd-Warshall also tolerates negative edge weights (though not negative cycles, which show up as a negative value appearing on the diagonal, dist[i][i] < 0, after the algorithm runs).