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.

Pour water in at A. Every road is a pipe whose length is its weight, and the water travels at the same speed everywhere. The water reaches each junction in order of its true distance: the nearest junction first, then the next nearest, and so on. Dijkstra simulates exactly that. At every step it handles the junction the water would reach next, and the moment it does, that junction's distance is settled, because no later water can arrive sooner.

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 of strategy. Instead of a plain queue, use a min-heap keyed by the total distance so far, and always pop whichever node currently has the smallest known distance from the start.

Each time a node is popped, relax its outgoing edges: if reaching a neighbor through this node is 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 unfinished node, a popped node's distance is final. Every other node still waiting already costs at least as much, so no later edge can beat it.

Using the graph from above (A to B: 4, A to C: 1, C to B: 2, B to D: 1, C to D: 5), starting from A:

• -The heap starts as [(0, A)]. Pop A: relax B to 4 and C to 1, and push (4, B) and (1, C).
• -Pop (1, C), the smallest. Relax B to 1 + 2 = 3, which beats 4, so push (3, B). Relax D to 1 + 5 = 6 and push (6, D).
• -Pop (3, B). Relax D to 3 + 1 = 4, which beats 6, so push (4, D).
• -Pop (4, B). But distances[B] is already 3, and 4 > 3, so this is a stale entry. Skip it without doing any work.
• -Pop (4, D). It is finalized, and D has no outgoing edges.
• -Pop (6, D). Stale again, since 4 < 6. Skip it.

The final distances from A are A = 0, B = 3, C = 1, D = 4. The route A to C to B to D beats the direct-looking A to B to D, an 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.

A second analogy helps here: Bellman-Ford is a rumor spreading through a town. In each round, every person passes on the best news they currently have. After one round the news has traveled one edge; after n - 1 rounds it has traveled as far as any shortest path can go.

Bellman-Ford answers the same single-source question as Dijkstra, but by a different strategy: instead of greedily expanding the cheapest known node, it relaxes every edge in the graph, n - 1 times, where n is the number of nodes.

The repetition is not arbitrary. With no negative-weight cycle, any shortest path uses at most n - 1 edges, and each full pass lets correct distances travel at least one more edge. So n - 1 passes are enough, in whatever order the edges are processed.

Because it never relies on once finalized, always final, it works correctly even when some edges are negative.

The extra nth pass has no equivalent in Dijkstra. If any edge can still be relaxed after n - 1 passes, distances are still shrinking after every legitimate shortest path should have settled. That can only happen when a negative-weight cycle reachable from the start lets a distance shrink for ever.

Returning None is the right answer then: no shortest path is defined when a cycle can be looped round to lower the cost without limit.

Both algorithms above answer a single-source question. Floyd-Warshall answers a different one: the shortest distance between every pair of nodes, all at once.

It is dynamic programming, not a traversal. After considering intermediate node k, dp[i][j] holds the shortest known distance from i to j using only nodes 0 through k as stops. Allowing one more intermediate node can only help if routing through it is cheaper, which is exactly the update rule.

The triple loop gives O(n^3) time and O(n^2) space, noticeably more than one Dijkstra run, but it buys every pair's distance at once.

Running Dijkstra from every node costs roughly O(n (n + e) log n). On a dense graph, where e is close to n^2, that can be slower than Floyd-Warshall's flat O(n^3), and it takes more code to get right.

Floyd-Warshall also tolerates negative edge weights, though not negative cycles, which show up as a negative value on the diagonal (dist[i][i] < 0) after it runs.