Data Structures & AlgorithmsDijkstra's Algorithm

Shortest Path — Dijkstra's Algorithm

LevelIntermediate

Duration90 mins

TopicDijkstra's Algorithm

3 / 5

The Relaxation Process

The Art of Finding Better Paths

At the heart of every shortest path algorithm lies a deceptively simple operation: relaxation. The term comes from physics and optimization, where we "relax" constraints to find better solutions. In the context of shortest paths, relaxation means asking: "Can we find a shorter path to this vertex by going through another vertex?"

This single operation, applied systematically, transforms our initial guess (all distances are infinity) into the exact shortest path distances. Understanding relaxation deeply reveals not just how Dijkstra's algorithm works, but why it works—and why it's provably correct.

What You Will Learn

By the end of this page, you will understand: (1) The formal definition of edge relaxation, (2) The triangle inequality and its role in shortest paths, (3) How relaxation drives convergence to correct distances, and (4) Why the order of relaxation matters for efficiency.

Defining Relaxation Formally

Edge relaxation is the operation of potentially improving the distance estimate to a vertex by using a newly discovered path. Let's define it precisely.

Setup:

We have a distance estimate array dist[] initialized with dist[source] = 0 and dist[v] = ∞ for all other vertices
We're examining an edge from u to v with weight w(u,v)

The relaxation operation:

To relax edge (u, v):

Compute the candidate distance: newDist = dist[u] + w(u, v)
If newDist < dist[v], update dist[v] = newDist

In words: if going through u provides a shorter path to v than our current best, update our estimate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Relax edge from u to v with given weight.
 * Returns true if the distance was improved.
 */
function relax(
    u: number, 
    v: number, 
    weight: number, 
    dist: number[], 
    parent: (number | null)[]
): boolean {
    const newDist = dist[u] + weight;
    
    if (newDist < dist[v]) {
        dist[v] = newDist;       // Update distance estimate
        parent[v] = u;           // Update path predecessor
        return true;             // Relaxation was successful
    }
    
    return false;  // No improvement
}
 
// Example usage in Dijkstra's loop:
for (const edge of graph[u]) {
    if (relax(u, edge.to, edge.weight, dist, parent)) {
        pq.insert(edge.to, dist[edge.to]);
    }
}

Key properties of relaxation:

Monotonicity: Relaxation never increases distance estimates—it can only decrease or maintain them
Correctness: If dist[u] = δ(s,u) (the true shortest path distance), then after relaxing edge (u,v), dist[v] ≤ δ(s,v)
Convergence: With enough relaxations in the right order, all estimates converge to true shortest path distances

Why "relaxation"?

The term comes from mathematical optimization. We start with a "tight" constraint (dist[v] = ∞, very pessimistic) and progressively "relax" it to better values. Each relaxation loosens our bound on the shortest path until we reach the true value.

Relaxation is Idempotent

Relaxing the same edge multiple times is safe—once dist[v] reaches its optimal value, subsequent relaxations of any edge to v will not change it. This means we can be liberal with relaxations without fear of "over-relaxing."

The Triangle Inequality

The mathematical foundation of relaxation is the triangle inequality, a fundamental property of shortest paths. Understanding this inequality explains why relaxation works and why it converges.

Statement of the Triangle Inequality:

For any vertices s, u, v and shortest path distances δ:

δ(s, v) ≤ δ(s, u) + δ(u, v)

The shortest path from s to v cannot be longer than the shortest path from s to u, plus the shortest path from u to v.

1
2
3
4
5
6
7
8
9
10
11
12
          s ─────────────────────────→ v
           \                           ↗
            \  δ(s,u)           δ(u,v)/
             \                      /
              ↘                    /
               u ────────────────→
 
    The direct path s→v (if it exists) cannot be longer than 
    going s→u→v, where each segment is the shortest path.
    
    If s→u→v were shorter than the direct shortest path s→v,
    then s→v wouldn't actually be the shortest path — contradiction!

Why does this matter for relaxation?

When we relax edge (u, v), we're testing whether the path s → ... → u → v is shorter than our current estimate for s → v. The triangle inequality guarantees:

If dist[u] = δ(s, u) (u's distance is correct)
And we relax edge (u, v)
Then dist[v] ≤ δ(s, u) + w(u, v)

Since w(u, v) ≥ δ(u, v) (a single edge can't be shorter than the shortest path), and the triangle inequality says δ(s, v) ≤ δ(s, u) + δ(u, v), relaxation can never set dist[v] below the true shortest path distance.

The invariant:

After any sequence of relaxations:

dist[v] ≥ δ(s, v) for all vertices v

Our estimates are always upper bounds on the true shortest path distances. Relaxation decreases these bounds toward the true values.

Upper Bound, Not Lower Bound

It's crucial to understand that dist[v] is always an upper bound. We start at ∞ (the loosest bound) and tighten toward δ(s,v). This is why starting with ∞ and reducing is correct, while starting with 0 and increasing would be wrong.

Relaxation and Path Optimality

The power of relaxation comes from a beautiful theorem: relaxing edges along a shortest path in order guarantees we find that shortest path. This is the key insight that makes shortest path algorithms work.

The Path Relaxation Property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Theorem: Let p = ⟨v₀, v₁, v₂, ..., vₖ⟩ be a shortest path from s = v₀ to vₖ.
         If we relax the edges of p in order:
         (v₀,v₁), (v₁,v₂), ..., (vₖ₋₁,vₖ)
         
         Then dist[vₖ] = δ(s, vₖ) after these relaxations.
 
Proof sketch:
  - After relaxing (v₀,v₁): dist[v₁] = δ(s,v₁) 
    (because dist[v₀] = dist[s] = 0 = δ(s,s))
  
  - After relaxing (v₁,v₂): dist[v₂] = δ(s,v₂)
    (because dist[v₁] is now correct)
  
  - By induction, after relaxing (vᵢ₋₁,vᵢ): dist[vᵢ] = δ(s,vᵢ)
  
  - Finally, dist[vₖ] = δ(s,vₖ) ✓

Why this matters for Dijkstra:

Dijkstra's algorithm doesn't know the shortest paths in advance—that's what it's trying to find! But the algorithm's structure ensures that when it relaxes edges, it does so in exactly the right order.

When we extract vertex u from the priority queue (the one with minimum distance), we're guaranteed that dist[u] is correct. Why? Because any shorter path to u would have to go through some vertex still in the queue, and all those vertices have larger distance estimates (that's why u was extracted first). With non-negative edges, going through a farther vertex can only make the path longer.

Since dist[u] is correct when we relax edges from u, the relaxations we perform propagate correct distances forward—exactly as the Path Relaxation Property requires.

Dijkstra Guarantees

•Vertices extracted in distance order
•Each vertex extracted exactly once
•Extraction = finalization (correct dist)
•Relaxations from finalized vertices

Resulting Properties

•Correct distances propagate outward
•Shortest paths discovered progressively
•Each edge relaxed at most once usefully
•Convergence in O(V + E) relaxations

Visualizing Relaxation in Action

Let's trace relaxation through a detailed example to see how distance estimates converge to true shortest paths. We'll observe each relaxation and its effect.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        S ────(10)───→ A ───(5)───→ C
        |              ↗ |
       (3)          (2)  (4)
        |          /      |
        ↓        /        ↓
        B ─────+          D
        |
       (6)
        |
        ↓
        E ────(1)───→ D
 
    Edges:
      S→A: 10,  S→B: 3
      B→A: 2,   B→E: 6
      A→C: 5,   A→D: 4
      E→D: 1
    
    Source: S
    We want shortest paths to all vertices.

Relaxation Trace — Step by Step
Step	Action	Edge	dist Before	dist After	Improved?
0	Initialize		S:∞,A:∞,B:∞,C:∞,D:∞,E:∞	S:0,A:∞,B:∞,C:∞,D:∞,E:∞
1	Extract S
2	Relax S→A	(S,A):10	A:∞	A:10	Yes ✓
3	Relax S→B	(S,B):3	B:∞	B:3	Yes ✓
4	Extract B (min=3)
5	Relax B→A	(B,A):2	A:10	A:5	Yes ✓ (3+2=5<10)
6	Relax B→E	(B,E):6	E:∞	E:9	Yes ✓
7	Extract A (min=5)
8	Relax A→C	(A,C):5	C:∞	C:10	Yes ✓
9	Relax A→D	(A,D):4	D:∞	D:9	Yes ✓
10	Extract E (min=9)
11	Relax E→D	(E,D):1	D:9	D:10	No ✗ (9+1>9)
12	Extract D (min=9)
13	D has no outgoing
14	Extract C (min=10)

Analysis of key relaxations:

Step 5 — B→A improves A's distance: Initially, S→A directly costs 10. But S→B→A costs 3+2=5. When we relax B→A, we discover this shorter path. This is why processing vertices in distance order matters: B (distance 3) was processed before A (initial distance 10), allowing us to find the better path.

Step 11 — E→D doesn't improve D's distance: We already have dist[D] = 9 from the path S→B→A→D. The path S→B→E→D would cost 3+6+1=10, which is worse. Relaxation correctly rejects this path.

Final shortest paths:

S: 0 (source)
B: 3 (S→B)
A: 5 (S→B→A)
D: 9 (S→B→A→D)
E: 9 (S→B→E)
C: 10 (S→B→A→C)

Failed Relaxations Are Informative

When a relaxation doesn't improve the distance, it's telling us something: we've already found a better path. This is not wasted work—it's confirmation that our current solution is at least as good as the alternative we just tested.

The Greedy Choice Property

Dijkstra's algorithm is a greedy algorithm—it makes locally optimal choices (process the minimum-distance vertex) that lead to a globally optimal solution (all shortest paths). This works because of a special property that non-negative edge weights provide.

The Greedy Choice Property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Theorem: Let u be the unprocessed vertex with minimum dist[u].
         Assume all processed vertices have correct shortest path distances.
         Then dist[u] = δ(s, u) — u's distance estimate is also correct.
 
Proof:
  Let p be the true shortest path from s to u.
  Let y be the first unprocessed vertex on path p.
  Let x be the vertex before y on path p (x is processed).
  
  The subpath s → ... → x → y has weight δ(s, y).
  Since x was processed, we relaxed edge (x, y), so:
      dist[y] ≤ dist[x] + w(x, y) = δ(s, y)
  
  But y is on the shortest path to u, so:
      δ(s, y) ≤ δ(s, u) ≤ dist[u]
  
  Since u has minimum dist among unprocessed vertices:
      dist[u] ≤ dist[y] ≤ δ(s, y) ≤ δ(s, u) ≤ dist[u]
  
  Therefore: dist[u] = δ(s, u)  ✓

Unpacking the proof:

We assume all processed vertices have correct distances (induction base: just the source)
Any path to u must start at the source (processed) and eventually enter unprocessed territory
The first unprocessed vertex y on the shortest path has its distances correctly bounded
Since u has minimum distance among unprocessed vertices, and y is also unprocessed...
Either u = y (u is directly on the shortest path from processed set), or dist[u] ≤ dist[y]
Either way, dist[u] equals the true shortest path distance

Why non-negative weights are essential:

The proof relies on δ(s, y) ≤ δ(s, u) when y comes before u on the path. This only holds if edges have non-negative weights! With negative edges, extending a path could decrease its weight, breaking this inequality.

The Non-Negative Requirement

The greedy choice works because 'farther' (more hops) means 'not closer' (in total weight). With negative edges, a path through more vertices could be shorter than a direct path. The fundamental assumption that 'minimum so far means minimum forever' collapses.

Relaxation Order and Efficiency

The order in which we relax edges dramatically affects algorithm efficiency. Different algorithms for shortest paths use different relaxation orders, with different consequences:

Dijkstra's order (greedy by distance):

Process vertices in order of increasing distance from source
Each vertex processed exactly once
Each edge relaxed exactly once (when its source vertex is processed)
Total relaxations: E
Works only with non-negative weights

Relaxation Strategies Compared
Algorithm	Relaxation Order	Total Relaxations	Constraints
Dijkstra	Greedy by distance	O(E) — once per edge	Non-negative weights only
Bellman-Ford	All edges, V-1 times	O(V × E)	Any weights (detects neg. cycles)
BFS (unweighted)	By discovery order	O(E) — once per edge	Unweighted graphs only
Random order	Arbitrary	Possibly unbounded	May not converge

Why Dijkstra's order is optimal:

Dijkstra's greedy order ensures that when we relax edges from a vertex, that vertex's distance is already correct. This means:

No redundant relaxations: An edge is relaxed once, when its source is finalized
No revisiting: Once a vertex is processed, its distance is final
Progressive correctness: Each extraction reveals another correct shortest path

Bellman-Ford's contrast:

Bellman-Ford handles negative weights by brute-forcing: relax all edges, then repeat V-1 times. Since we don't know the right order, we try everything and repeat enough times to guarantee convergence. This works but costs O(VE) instead of O(E log V).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Consider a path s → a → b → c (shortest path to c)
 
Dijkstra's approach:
  1. Process s, relax s→a: dist[a] = correct ✓
  2. Process a (minimum distance), relax a→b: dist[b] = correct ✓
  3. Process b (minimum distance), relax b→c: dist[c] = correct ✓
  Total: 3 relaxations along this path, each edge once.
 
Random approach:
  - Might relax c→b first (useless)
  - Then a→b (useful)
  - Then s→a (useful, but now must re-relax a→b)
  - Then c→b again to propagate
  Potentially many wasted or repeated relaxations.
 
The greedy order eliminates waste by ensuring prerequisites 
are satisfied before relaxation.

The Priority Queue is the Hero

The priority queue isn't just an implementation detail—it enforces the relaxation order that makes Dijkstra efficient. By always extracting the minimum-distance vertex, we guarantee that we relax edges in exactly the order that propagates correct distances without backtracking.

Relaxation Invariants

To prove Dijkstra's algorithm correct formally, we establish invariants—properties that hold true throughout execution. These invariants are maintained by the relaxation process.

Key invariants of Dijkstra's algorithm:

Algorithm Invariants

•Upper Bound Property: For all v, dist[v] ≥ δ(s, v). Distance estimates are always upper bounds on true shortest paths.
•Finalization Property: If v is in the processed set, then dist[v] = δ(s, v). Processed vertices have exact shortest path distances.
•Convergence Property: At termination, dist[v] = δ(s, v) for all reachable vertices. The algorithm finds all shortest paths.
•Path Property: If dist[v] < ∞ and parent[v] = u, then the path defined by parent pointers is a shortest path.

How relaxation maintains these invariants:

Upper Bound Property:

Initially, dist[s] = 0 = δ(s, s), and dist[v] = ∞ ≥ δ(s, v) for others
Relaxation sets dist[v] = dist[u] + w(u, v)
If dist[u] ≥ δ(s, u), then dist[v] ≥ δ(s, u) + w(u, v) ≥ δ(s, v) (by triangle inequality)
So relaxation never violates the upper bound

Finalization Property:

When we extract u (minimum distance among unprocessed), the Greedy Choice Property guarantees dist[u] = δ(s, u)
Adding u to the processed set maintains the invariant

Together: The invariants form a proof scaffold. We maintain invariants through each step, and at termination, the invariants give us the desired result: all distances are correct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Proof of Correctness:
 
Initialization:
  - dist[s] = 0 = δ(s, s) ✓
  - dist[v] = ∞ ≥ δ(s, v) for v ≠ s ✓
  - Processed set is empty (vacuously true) ✓
 
Maintenance (each iteration):
  Let u = extractMin() from unprocessed vertices
  Claim: dist[u] = δ(s, u)
  
  Proof: Greedy Choice Property (shown earlier) ✓
  
  After adding u to processed set:
  - All previously processed vertices still have correct distances ✓
  - u now has correct distance ✓
  - Finalization Property maintained ✓
 
Termination:
  - All reachable vertices eventually processed
  - By Finalization Property, all have correct distances ✓
 
Therefore: Dijkstra's algorithm is correct.  ∎

Invariants as Debugging Tools

When implementing Dijkstra, you can add assertions to check invariants. If an invariant fails, you've found a bug. Common issues: forgetting to initialize the source distance, using a max-heap instead of min-heap, or processing vertices more than once.

Summary: The Power of Relaxation

Relaxation is the atomic operation that drives all shortest path algorithms. We've explored its formal definition, theoretical foundations, and role in Dijkstra's algorithm. Let's consolidate:

Key Takeaways

•Relaxation tests for shorter paths — For edge (u, v), check if dist[u] + w(u, v) < dist[v]; if so, update.
•Triangle inequality ensures correctness — Shortest path distances obey δ(s, v) ≤ δ(s, u) + δ(u, v).
•Path relaxation property — Relaxing edges of a shortest path in order produces correct distances.
•Greedy choice is safe — With non-negative weights, the minimum-distance unprocessed vertex has a correct distance.
•Order matters for efficiency — Dijkstra's greedy order enables O(E) total relaxations; arbitrary order can be much worse.
•Invariants prove correctness — Upper bounds, finalization, and convergence properties are maintained throughout.

What's next:

We've established that Dijkstra's algorithm works and why. The next page examines time complexity analysis—deriving the O((V + E) log V) bound, comparing implementation approaches, and understanding where the time goes in practice.

Page Complete

You now deeply understand edge relaxation, the theoretical foundations that make it work (triangle inequality, path relaxation property), and how Dijkstra's greedy extraction order leads to efficient, correct shortest path computation. Next, we'll quantify the algorithm's efficiency through rigorous complexity analysis.

3 / 5

Loading learning content...

Data Structures & AlgorithmsDijkstra's Algorithm

Shortest Path — Dijkstra's Algorithm

LevelIntermediate

Duration90 mins

TopicDijkstra's Algorithm

3 / 5

The Relaxation Process

The Art of Finding Better Paths

What You Will Learn

Defining Relaxation Formally

Edge relaxation is the operation of potentially improving the distance estimate to a vertex by using a newly discovered path. Let's define it precisely.

Setup:

We have a distance estimate array dist[] initialized with dist[source] = 0 and dist[v] = ∞ for all other vertices
We're examining an edge from u to v with weight w(u,v)

The relaxation operation:

To relax edge (u, v):

Compute the candidate distance: newDist = dist[u] + w(u, v)
If newDist < dist[v], update dist[v] = newDist

In words: if going through u provides a shorter path to v than our current best, update our estimate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Relax edge from u to v with given weight.
 * Returns true if the distance was improved.
 */
function relax(
    u: number, 
    v: number, 
    weight: number, 
    dist: number[], 
    parent: (number | null)[]
): boolean {
    const newDist = dist[u] + weight;
    
    if (newDist < dist[v]) {
        dist[v] = newDist;       // Update distance estimate
        parent[v] = u;           // Update path predecessor
        return true;             // Relaxation was successful
    }
    
    return false;  // No improvement
}
 
// Example usage in Dijkstra's loop:
for (const edge of graph[u]) {
    if (relax(u, edge.to, edge.weight, dist, parent)) {
        pq.insert(edge.to, dist[edge.to]);
    }
}

Key properties of relaxation:

Monotonicity: Relaxation never increases distance estimates—it can only decrease or maintain them
Correctness: If dist[u] = δ(s,u) (the true shortest path distance), then after relaxing edge (u,v), dist[v] ≤ δ(s,v)
Convergence: With enough relaxations in the right order, all estimates converge to true shortest path distances

Why "relaxation"?

Relaxation is Idempotent

The Triangle Inequality

The mathematical foundation of relaxation is the triangle inequality, a fundamental property of shortest paths. Understanding this inequality explains why relaxation works and why it converges.

Statement of the Triangle Inequality:

For any vertices s, u, v and shortest path distances δ:

δ(s, v) ≤ δ(s, u) + δ(u, v)

The shortest path from s to v cannot be longer than the shortest path from s to u, plus the shortest path from u to v.

1
2
3
4
5
6
7
8
9
10
11
12
          s ─────────────────────────→ v
           \                           ↗
            \  δ(s,u)           δ(u,v)/
             \                      /
              ↘                    /
               u ────────────────→
 
    The direct path s→v (if it exists) cannot be longer than 
    going s→u→v, where each segment is the shortest path.
    
    If s→u→v were shorter than the direct shortest path s→v,
    then s→v wouldn't actually be the shortest path — contradiction!

Why does this matter for relaxation?

When we relax edge (u, v), we're testing whether the path s → ... → u → v is shorter than our current estimate for s → v. The triangle inequality guarantees:

If dist[u] = δ(s, u) (u's distance is correct)
And we relax edge (u, v)
Then dist[v] ≤ δ(s, u) + w(u, v)

The invariant:

After any sequence of relaxations:

dist[v] ≥ δ(s, v) for all vertices v

Our estimates are always upper bounds on the true shortest path distances. Relaxation decreases these bounds toward the true values.

Upper Bound, Not Lower Bound

Relaxation and Path Optimality

The Path Relaxation Property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Theorem: Let p = ⟨v₀, v₁, v₂, ..., vₖ⟩ be a shortest path from s = v₀ to vₖ.
         If we relax the edges of p in order:
         (v₀,v₁), (v₁,v₂), ..., (vₖ₋₁,vₖ)
         
         Then dist[vₖ] = δ(s, vₖ) after these relaxations.
 
Proof sketch:
  - After relaxing (v₀,v₁): dist[v₁] = δ(s,v₁) 
    (because dist[v₀] = dist[s] = 0 = δ(s,s))
  
  - After relaxing (v₁,v₂): dist[v₂] = δ(s,v₂)
    (because dist[v₁] is now correct)
  
  - By induction, after relaxing (vᵢ₋₁,vᵢ): dist[vᵢ] = δ(s,vᵢ)
  
  - Finally, dist[vₖ] = δ(s,vₖ) ✓

Why this matters for Dijkstra:

Since dist[u] is correct when we relax edges from u, the relaxations we perform propagate correct distances forward—exactly as the Path Relaxation Property requires.

Dijkstra Guarantees

•Vertices extracted in distance order
•Each vertex extracted exactly once
•Extraction = finalization (correct dist)
•Relaxations from finalized vertices

Resulting Properties

•Correct distances propagate outward
•Shortest paths discovered progressively
•Each edge relaxed at most once usefully
•Convergence in O(V + E) relaxations

Visualizing Relaxation in Action

Let's trace relaxation through a detailed example to see how distance estimates converge to true shortest paths. We'll observe each relaxation and its effect.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        S ────(10)───→ A ───(5)───→ C
        |              ↗ |
       (3)          (2)  (4)
        |          /      |
        ↓        /        ↓
        B ─────+          D
        |
       (6)
        |
        ↓
        E ────(1)───→ D
 
    Edges:
      S→A: 10,  S→B: 3
      B→A: 2,   B→E: 6
      A→C: 5,   A→D: 4
      E→D: 1
    
    Source: S
    We want shortest paths to all vertices.

Relaxation Trace — Step by Step
Step	Action	Edge	dist Before	dist After	Improved?
0	Initialize		S:∞,A:∞,B:∞,C:∞,D:∞,E:∞	S:0,A:∞,B:∞,C:∞,D:∞,E:∞
1	Extract S
2	Relax S→A	(S,A):10	A:∞	A:10	Yes ✓
3	Relax S→B	(S,B):3	B:∞	B:3	Yes ✓
4	Extract B (min=3)
5	Relax B→A	(B,A):2	A:10	A:5	Yes ✓ (3+2=5<10)
6	Relax B→E	(B,E):6	E:∞	E:9	Yes ✓
7	Extract A (min=5)
8	Relax A→C	(A,C):5	C:∞	C:10	Yes ✓
9	Relax A→D	(A,D):4	D:∞	D:9	Yes ✓
10	Extract E (min=9)
11	Relax E→D	(E,D):1	D:9	D:10	No ✗ (9+1>9)
12	Extract D (min=9)
13	D has no outgoing
14	Extract C (min=10)

Analysis of key relaxations:

Final shortest paths:

S: 0 (source)
B: 3 (S→B)
A: 5 (S→B→A)
D: 9 (S→B→A→D)
E: 9 (S→B→E)
C: 10 (S→B→A→C)

Failed Relaxations Are Informative

The Greedy Choice Property

The Greedy Choice Property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Theorem: Let u be the unprocessed vertex with minimum dist[u].
         Assume all processed vertices have correct shortest path distances.
         Then dist[u] = δ(s, u) — u's distance estimate is also correct.
 
Proof:
  Let p be the true shortest path from s to u.
  Let y be the first unprocessed vertex on path p.
  Let x be the vertex before y on path p (x is processed).
  
  The subpath s → ... → x → y has weight δ(s, y).
  Since x was processed, we relaxed edge (x, y), so:
      dist[y] ≤ dist[x] + w(x, y) = δ(s, y)
  
  But y is on the shortest path to u, so:
      δ(s, y) ≤ δ(s, u) ≤ dist[u]
  
  Since u has minimum dist among unprocessed vertices:
      dist[u] ≤ dist[y] ≤ δ(s, y) ≤ δ(s, u) ≤ dist[u]
  
  Therefore: dist[u] = δ(s, u)  ✓

Unpacking the proof:

We assume all processed vertices have correct distances (induction base: just the source)
Any path to u must start at the source (processed) and eventually enter unprocessed territory
The first unprocessed vertex y on the shortest path has its distances correctly bounded
Since u has minimum distance among unprocessed vertices, and y is also unprocessed...
Either u = y (u is directly on the shortest path from processed set), or dist[u] ≤ dist[y]
Either way, dist[u] equals the true shortest path distance

Why non-negative weights are essential:

The Non-Negative Requirement

Relaxation Order and Efficiency

The order in which we relax edges dramatically affects algorithm efficiency. Different algorithms for shortest paths use different relaxation orders, with different consequences:

Dijkstra's order (greedy by distance):

Process vertices in order of increasing distance from source
Each vertex processed exactly once
Each edge relaxed exactly once (when its source vertex is processed)
Total relaxations: E
Works only with non-negative weights

Relaxation Strategies Compared
Algorithm	Relaxation Order	Total Relaxations	Constraints
Dijkstra	Greedy by distance	O(E) — once per edge	Non-negative weights only
Bellman-Ford	All edges, V-1 times	O(V × E)	Any weights (detects neg. cycles)
BFS (unweighted)	By discovery order	O(E) — once per edge	Unweighted graphs only
Random order	Arbitrary	Possibly unbounded	May not converge

Why Dijkstra's order is optimal:

Dijkstra's greedy order ensures that when we relax edges from a vertex, that vertex's distance is already correct. This means:

No redundant relaxations: An edge is relaxed once, when its source is finalized
No revisiting: Once a vertex is processed, its distance is final
Progressive correctness: Each extraction reveals another correct shortest path

Bellman-Ford's contrast:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Consider a path s → a → b → c (shortest path to c)
 
Dijkstra's approach:
  1. Process s, relax s→a: dist[a] = correct ✓
  2. Process a (minimum distance), relax a→b: dist[b] = correct ✓
  3. Process b (minimum distance), relax b→c: dist[c] = correct ✓
  Total: 3 relaxations along this path, each edge once.
 
Random approach:
  - Might relax c→b first (useless)
  - Then a→b (useful)
  - Then s→a (useful, but now must re-relax a→b)
  - Then c→b again to propagate
  Potentially many wasted or repeated relaxations.
 
The greedy order eliminates waste by ensuring prerequisites 
are satisfied before relaxation.

The Priority Queue is the Hero

Relaxation Invariants

To prove Dijkstra's algorithm correct formally, we establish invariants—properties that hold true throughout execution. These invariants are maintained by the relaxation process.

Key invariants of Dijkstra's algorithm:

Algorithm Invariants

•Upper Bound Property: For all v, dist[v] ≥ δ(s, v). Distance estimates are always upper bounds on true shortest paths.
•Finalization Property: If v is in the processed set, then dist[v] = δ(s, v). Processed vertices have exact shortest path distances.
•Convergence Property: At termination, dist[v] = δ(s, v) for all reachable vertices. The algorithm finds all shortest paths.
•Path Property: If dist[v] < ∞ and parent[v] = u, then the path defined by parent pointers is a shortest path.

How relaxation maintains these invariants:

Upper Bound Property:

Initially, dist[s] = 0 = δ(s, s), and dist[v] = ∞ ≥ δ(s, v) for others
Relaxation sets dist[v] = dist[u] + w(u, v)
If dist[u] ≥ δ(s, u), then dist[v] ≥ δ(s, u) + w(u, v) ≥ δ(s, v) (by triangle inequality)
So relaxation never violates the upper bound

Finalization Property:

When we extract u (minimum distance among unprocessed), the Greedy Choice Property guarantees dist[u] = δ(s, u)
Adding u to the processed set maintains the invariant

Together: The invariants form a proof scaffold. We maintain invariants through each step, and at termination, the invariants give us the desired result: all distances are correct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Proof of Correctness:
 
Initialization:
  - dist[s] = 0 = δ(s, s) ✓
  - dist[v] = ∞ ≥ δ(s, v) for v ≠ s ✓
  - Processed set is empty (vacuously true) ✓
 
Maintenance (each iteration):
  Let u = extractMin() from unprocessed vertices
  Claim: dist[u] = δ(s, u)
  
  Proof: Greedy Choice Property (shown earlier) ✓
  
  After adding u to processed set:
  - All previously processed vertices still have correct distances ✓
  - u now has correct distance ✓
  - Finalization Property maintained ✓
 
Termination:
  - All reachable vertices eventually processed
  - By Finalization Property, all have correct distances ✓
 
Therefore: Dijkstra's algorithm is correct.  ∎

Invariants as Debugging Tools

Summary: The Power of Relaxation

Relaxation is the atomic operation that drives all shortest path algorithms. We've explored its formal definition, theoretical foundations, and role in Dijkstra's algorithm. Let's consolidate:

Key Takeaways

•Relaxation tests for shorter paths — For edge (u, v), check if dist[u] + w(u, v) < dist[v]; if so, update.
•Triangle inequality ensures correctness — Shortest path distances obey δ(s, v) ≤ δ(s, u) + δ(u, v).
•Path relaxation property — Relaxing edges of a shortest path in order produces correct distances.
•Greedy choice is safe — With non-negative weights, the minimum-distance unprocessed vertex has a correct distance.
•Order matters for efficiency — Dijkstra's greedy order enables O(E) total relaxations; arbitrary order can be much worse.
•Invariants prove correctness — Upper bounds, finalization, and convergence properties are maintained throughout.

What's next:

Page Complete

3 / 5