Correctness of Dijkstra's Algorithm
You'll learn: Why Dijkstra's greedy approach of always picking the nearest unvisited node guarantees the shortest path when all edge weights are non-negative.
The Core Proof Idea
Dijkstra's algorithm works by maintaining a set of nodes whose shortest distances from the source are finalized. Each iteration, it greedily picks the unvisited node with the smallest tentative distance and finalizes it. But why can we be sure this greedy choice is correct?
The key insight: Once a node is finalized, no future discovery can offer a shorter path to it (assuming non-negative weights).
Why the Greedy Choice Works
Imagine you're at a node u that's just been selected with distance d[u]. Could there be a shorter path to u through some other unvisited node v?
No, here's why:
- Any path to
uthrough an unvisited nodevmust first reachv - The distance to reach
vis at leastd[v](its current tentative distance) - Since we chose
uoverv, we knowd[u] ≤ d[v] - Even if we reach
vand then travel tou, the total distance isd[v] + (cost from v to u) - With non-negative weights, this is
≥ d[v] ≥ d[u]
So the direct path to u can't be beaten by any detour!
The Non-Negative Weight Requirement
If edges could have negative weights, a longer detour path could accumulate enough "negative cost" to become shorter than the direct path. This breaks the greedy assumption. That's why Dijkstra requires non-negative weights.
Key Takeaway: Dijkstra's correctness relies on the fact that with non-negative weights, once you've found the shortest way to reach a node, no future path through more distant nodes can improve it—making the greedy choice provably optimal.