Course contentsShow
← Computer Science
Lesson 970 of 2,87223. Shortest Path AlgorithmsFree lesson

Correctness of Dijkstra's Algorithm

Proving that Dijkstra's greedy choice always yields optimal shortest paths with non-negative weights.

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 u through an unvisited node v must first reach v
  • The distance to reach v is at least d[v] (its current tentative distance)
  • Since we chose u over v, we know d[u] ≤ d[v]
  • Even if we reach v and then travel to u, the total distance is d[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.