Chapter 24: Single-Source Shortest Paths

Given a weighted, directed graph G = (V, E) with weight function w: E → ℝ, the weight of a path p = ⟨v₀, v₁, ..., vₖ⟩ is:

w(p) = Σᵢ₌₁ᵏ w(vᵢ₋₁, vᵢ)

The shortest-path weight δ(u, v) from u to v is defined as:

• δ(u, v) = min{w(p) : u →ᵖ v} if a path from u to v exists
• δ(u, v) = ∞ otherwise

A shortest path from u to v is any path p with w(p) = δ(u, v).

Variants of Shortest-Path Problems

• Single-source: Find shortest paths from a source s to all vertices (this chapter's focus)
• Single-destination: Find shortest paths from all vertices to a destination t (reverse edges → single-source)
• Single-pair: Find a shortest path from u to v (no known algorithm faster than best single-source)
• All-pairs: Find shortest paths between every pair of vertices (Chapter 25)

Optimal Substructure

Lemma 24.1 (Subpaths of shortest paths are shortest paths): Given a shortest path p = ⟨v₀, v₁, ..., vₖ⟩, any subpath pᵢⱼ = ⟨vᵢ, vᵢ₊₁, ..., vⱼ⟩ is a shortest path from vᵢ to vⱼ.

Proof sketch: If a shorter subpath p'ᵢⱼ existed, we could substitute it into p to get a path from v₀ to vₖ with weight less than w(p), contradicting that p is a shortest path.

Negative-Weight Edges

• If G contains no negative-weight cycles reachable from s, then δ(s, v) is well-defined for all v ∈ V (may be negative)
• If a negative-weight cycle is reachable from s and lies on a path from s to v, then δ(s, v) = −∞
• Shortest paths cannot contain positive-weight cycles (removing the cycle reduces weight)
• Zero-weight cycles can be removed without changing path weight
• Therefore, shortest paths are simple (cycle-free) and contain at most |V| − 1 edges

Representing Shortest Paths

For each vertex v, maintain a predecessor v.π (another vertex or NIL). The chain of predecessors traces back along a shortest path from s to v.

The predecessor subgraph Gπ = (Vπ, Eπ):

• Vπ = {v ∈ V : v.π ≠ NIL} ∪ {s}
• Eπ = {(v.π, v) ∈ E : v ∈ Vπ − {s}}

A shortest-paths tree rooted at s is a directed subgraph G' = (V', E') where:

1. V' is the set of vertices reachable from s in G
2. G' forms a rooted tree with root s
3. For all v ∈ V', the unique simple path from s to v in G' is a shortest path from s to v in G

Relaxation

The central technique used by all algorithms in this chapter.

Initialization

INITIALIZE-SINGLE-SOURCE(G, s)
1  for each vertex v ∈ G.V
2      v.d = ∞
3      v.π = NIL
4  s.d = 0

Relaxing an Edge

RELAX(u, v, w)
1  if v.d > u.d + w(u, v)
2      v.d = u.d + w(u, v)
3      v.π = u

Relaxation tests whether the shortest path to v can be improved by going through u. If so, it updates v.d (the shortest-path estimate) and v.π. Runs in O(1) time.

Key Properties of Shortest Paths and Relaxation

These properties assume the graph has been initialized with INITIALIZE-SINGLE-SOURCE and that shortest-path estimates change only via relaxation.

1. Triangle inequality (Lemma 24.10): For any edge (u, v) ∈ E: δ(s, v) ≤ δ(s, u) + w(u, v)
2. Upper-bound property (Lemma 24.11): v.d ≥ δ(s, v) always, and once v.d = δ(s, v), it never changes
3. No-path property (Corollary 24.12): If no path from s to v exists, then v.d = δ(s, v) = ∞ always
4. Convergence property (Lemma 24.14): If s ⇝ u → v is a shortest path and u.d = δ(s, u) before relaxing (u, v), then v.d = δ(s, v) afterward
5. Path-relaxation property (Lemma 24.15): If p = ⟨v₀, v₁, ..., vₖ⟩ is a shortest path from s = v₀ to vₖ, and edges are relaxed in order (v₀,v₁), (v₁,v₂), ..., (vₖ₋₁,vₖ), then vₖ.d = δ(s, vₖ) — regardless of any other intermixed relaxations
6. Predecessor-subgraph property (Lemma 24.17): Once v.d = δ(s, v) for all v ∈ V, the predecessor subgraph Gπ is a shortest-paths tree rooted at s

---

24.1 The Bellman-Ford Algorithm

Solves single-source shortest paths in the general case where edge weights may be negative. Returns TRUE if no negative-weight cycle is reachable from s; returns FALSE otherwise.

Algorithm

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i = 1 to |G.V| - 1
3      for each edge (u, v) ∈ G.E
4          RELAX(u, v, w)
5  for each edge (u, v) ∈ G.E
6      if v.d > u.d + w(u, v)
7          return FALSE
8  return TRUE

How It Works

1. Initialize all shortest-path estimates to ∞ (source to 0)
2. Make |V| − 1 passes over all edges, relaxing each edge in every pass
3. Check for negative-weight cycles: if any edge can still be relaxed, a negative-weight cycle exists

Running Time

O(VE): Initialization is Θ(V), the |V| − 1 passes each take Θ(E), and the final check takes O(E).

Correctness

Lemma 24.2: If G has no negative-weight cycles reachable from s, then after |V| − 1 iterations, v.d = δ(s, v) for all reachable vertices v.

• Proof: Consider any shortest path p = ⟨v₀, v₁, ..., vₖ⟩ from s to v. Since shortest paths are simple, k ≤ |V| − 1. In the iᵗʰ iteration, edge (vᵢ₋₁, vᵢ) is relaxed. By the path-relaxation property, v.d = δ(s, v) after all iterations.

Theorem 24.4 (Correctness of Bellman-Ford):

• If G has no negative-weight cycle reachable from s: returns TRUE, v.d = δ(s, v) for all v, and Gπ is a shortest-paths tree
• If G has a negative-weight cycle reachable from s: returns FALSE

Proof of negative-cycle detection: Assume for contradiction that the algorithm returns TRUE despite a negative-weight cycle c = ⟨v₀, v₁, ..., vₖ⟩ (where v₀ = vₖ). Then vᵢ.d ≤ vᵢ₋₁.d + w(vᵢ₋₁, vᵢ) for all i. Summing around the cycle, the left and right d-sums cancel (each vertex appears once), yielding 0 ≤ Σw(vᵢ₋₁, vᵢ) = w(c), contradicting that c is a negative-weight cycle.

---

24.2 Single-Source Shortest Paths in DAGs

Computes shortest paths from a single source in a directed acyclic graph (DAG) in Θ(V + E) time. Works even with negative-weight edges (no cycles exist in a DAG, so no negative-weight cycles).

Algorithm

DAG-SHORTEST-PATHS(G, w, s)
1  topologically sort the vertices of G
2  INITIALIZE-SINGLE-SOURCE(G, s)
3  for each vertex u, taken in topologically sorted order
4      for each vertex v ∈ G.Adj[u]
5          RELAX(u, v, w)

How It Works

1. Topologically sort the vertices (linear ordering such that if (u, v) ∈ E, then u precedes v)
2. Initialize shortest-path estimates
3. Process vertices in topological order; for each vertex, relax all outgoing edges

Running Time

Θ(V + E): Topological sort takes Θ(V + E), initialization takes Θ(V), and each edge is relaxed exactly once.

Correctness

Theorem 24.5: At termination, v.d = δ(s, v) for all v ∈ V, and Gπ is a shortest-paths tree.

• Proof: If v is unreachable from s, the no-path property gives v.d = ∞ = δ(s, v). If v is reachable, consider a shortest path p = ⟨v₀, v₁, ..., vₖ⟩. Since vertices are processed in topological order, edges on p are relaxed in order. By the path-relaxation property, vₖ.d = δ(s, vₖ). The predecessor-subgraph property gives the tree.

Application: Critical Paths (PERT Charts)

• Edges represent jobs; weights represent durations
• A critical path is a longest path through the DAG (lower bound on total completion time)
• Find critical paths by either:
  • Negating edge weights and running DAG-SHORTEST-PATHS
  • Modifying initialization to use −∞ instead of ∞ and reversing the comparison in RELAX (use "<" instead of ">")

---

24.3 Dijkstra's Algorithm

Solves single-source shortest paths when all edge weights are nonnegative (w(u, v) ≥ 0 for all edges). Faster than Bellman-Ford.

Algorithm

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  S = ∅
3  Q = G.V                          // min-priority queue keyed by d values
4  while Q ≠ ∅
5      u = EXTRACT-MIN(Q)
6      S = S ∪ {u}
7      for each vertex v ∈ G.Adj[u]
8          RELAX(u, v, w)

How It Works

1. Maintain a set S of vertices whose final shortest-path weights are determined
2. Use a min-priority queue Q = V − S, keyed by d values
3. Repeatedly extract the vertex u with minimum d from Q, add u to S, and relax all edges leaving u
4. Invariant: Q = V − S at the start of each iteration

This is a greedy algorithm — it always selects the closest unprocessed vertex.

Correctness

Theorem 24.6: Dijkstra's algorithm terminates with u.d = δ(s, u) for all u ∈ V.

Proof (by loop invariant — v.d = δ(s, v) for all v ∈ S):

• Initialization: S = ∅, trivially true
• Maintenance: Suppose u is the first vertex added to S with u.d ≠ δ(s, u). Let p be a shortest path from s to u. Let y be the first vertex on p not in S, with predecessor x ∈ S on p. Since x was added to S correctly, x.d = δ(s, x). Edge (x, y) was relaxed when x was added, so y.d = δ(s, y) by the convergence property. Since all weights are nonnegative: δ(s, y) ≤ δ(s, u) ≤ u.d. But u was chosen as the minimum in Q, so u.d ≤ y.d. Combining: y.d = δ(s, y) = δ(s, u) = u.d — contradiction.
• Termination: Q = ∅ implies S = V, so all vertices have correct shortest-path weights

Corollary 24.7: At termination, Gπ is a shortest-paths tree rooted at s.

Running Time Analysis

The running time depends on the priority queue implementation:

• Array: Best for dense graphs (E = Θ(V²))
• Binary heap: Better when E = o(V² / lg V)
• Fibonacci heap: Best asymptotically for sparse graphs; motivated by the observation that Dijkstra's makes many more DECREASE-KEY calls than EXTRACT-MIN calls

Comparison with Other Algorithms

• Similar to BFS: set S corresponds to black vertices; vertices in S have final distances
• Similar to Prim's MST algorithm: both use a min-priority queue to greedily select the "lightest" vertex outside a growing set

---

24.4 Difference Constraints and Shortest Paths

A special case of linear programming that reduces to single-source shortest paths.

Systems of Difference Constraints

A system of difference constraints is a set of m inequalities on n unknowns of the form:

xⱼ − xᵢ ≤ bₖ

Each row of the constraint matrix A has exactly one 1 and one −1 (all other entries are 0).

Lemma 24.8: If x = (x₁, x₂, ..., xₙ) is a solution, then x + d = (x₁ + d, x₂ + d, ..., xₙ + d) is also a solution for any constant d.

• Proof: (xⱼ + d) − (xᵢ + d) = xⱼ − xᵢ, so all constraints are preserved.

Constraint Graphs

Given a system Ax ≤ b, the constraint graph G = (V, E) is defined as:

• V = {v₀, v₁, ..., vₙ} — one vertex per unknown, plus an extra source vertex v₀
• E contains:
  • Edge (vᵢ, vⱼ) with weight bₖ for each constraint xⱼ − xᵢ ≤ bₖ
  • Edge (v₀, vᵢ) with weight 0 for each unknown xᵢ (ensures all vertices are reachable from v₀)

Solving via Shortest Paths

Theorem 24.9: Given a system Ax ≤ b with constraint graph G:

• If G has no negative-weight cycle: x = (δ(v₀, v₁), δ(v₀, v₂), ..., δ(v₀, vₙ)) is a feasible solution
• If G has a negative-weight cycle: no feasible solution exists

Proof of feasibility: For any constraint edge (vᵢ, vⱼ) with weight w(vᵢ, vⱼ) = bₖ, the triangle inequality gives δ(v₀, vⱼ) ≤ δ(v₀, vᵢ) + w(vᵢ, vⱼ). Setting xᵢ = δ(v₀, vᵢ) and xⱼ = δ(v₀, vⱼ) satisfies xⱼ − xᵢ ≤ bₖ.

Proof of infeasibility: A negative-weight cycle c = ⟨v₁, v₂, ..., vₖ⟩ (where v₁ = vₖ) corresponds to constraints that, when summed, yield 0 ≤ w(c) < 0 — a contradiction.

Algorithm

1. Construct the constraint graph G (n + 1 vertices, n + m edges)
2. Run Bellman-Ford from vertex v₀
3. If Bellman-Ford returns TRUE: shortest-path weights give a feasible solution
4. If Bellman-Ford returns FALSE: no feasible solution exists

Running time: O((n + 1)(n + m)) = O(n² + nm)

Application Example

Difference constraints model scheduling problems where events must occur within certain time intervals of each other (e.g., job scheduling with precedence and timing constraints).

---

24.5 Proofs of Shortest-Paths Properties

Triangle Inequality

Lemma 24.10: For all edges (u, v) ∈ E: δ(s, v) ≤ δ(s, u) + w(u, v).

Proof: A shortest path from s to v has weight no more than any path from s to v. In particular, it weighs no more than the path that takes a shortest path from s to u followed by edge (u, v).

Upper-Bound Property

Lemma 24.11: After INITIALIZE-SINGLE-SOURCE, v.d ≥ δ(s, v) for all v ∈ V, and this invariant is maintained over any sequence of relaxation steps. Once v.d = δ(s, v), it never changes.

Proof by induction on relaxation steps:

• Base: After initialization, s.d = 0 ≥ δ(s, s) and v.d = ∞ ≥ δ(s, v) for v ≠ s
• Inductive step: When relaxing (u, v), if v.d changes: v.d = u.d + w(u, v) ≥ δ(s, u) + w(u, v) ≥ δ(s, v) (by inductive hypothesis and triangle inequality)
• Once v.d = δ(s, v): cannot decrease (lower bound proven above), cannot increase (relaxation only decreases d values)

No-Path Property

Corollary 24.12: If no path from s to v exists, then v.d = δ(s, v) = ∞ always.

Proof: By upper-bound property, ∞ = δ(s, v) ≤ v.d, so v.d = ∞.

Convergence Property

Lemma 24.14: If s ⇝ u → v is a shortest path and u.d = δ(s, u) before relaxing (u, v), then v.d = δ(s, v) afterward.

Proof: After relaxing (u, v), by Lemma 24.13: v.d ≤ u.d + w(u, v) = δ(s, u) + w(u, v) = δ(s, v) (by Lemma 24.1). Combined with the upper-bound property (v.d ≥ δ(s, v)), we get v.d = δ(s, v).

Path-Relaxation Property

Lemma 24.15: If p = ⟨v₀, v₁, ..., vₖ⟩ is a shortest path from s = v₀ to vₖ, and edges are relaxed in order (v₀,v₁), (v₁,v₂), ..., (vₖ₋₁,vₖ), then vₖ.d = δ(s, vₖ). This holds regardless of any other intermixed relaxation steps.

Proof by induction:

• Base (i = 0): v₀.d = s.d = 0 = δ(s, s) after initialization
• Inductive step: Assume vᵢ₋₁.d = δ(s, vᵢ₋₁). After relaxing (vᵢ₋₁, vᵢ), the convergence property gives vᵢ.d = δ(s, vᵢ).

Predecessor-Subgraph Property

Lemma 24.16: After initialization, Gπ forms a rooted tree with root s, and this is maintained as an invariant over any sequence of relaxation steps (assuming no negative-weight cycles reachable from s).

Proof sketch:

• Acyclicity: Suppose relaxation creates a cycle c in Gπ. Summing the d-inequalities around c yields 0 > w(c), meaning c is a negative-weight cycle — contradicting the assumption.
• Unique paths: If two simple paths from s to v existed in Gπ, some vertex z would have two distinct predecessors, which is impossible since z.π is a single value.

Lemma 24.17 (Predecessor-subgraph property): If v.d = δ(s, v) for all v ∈ V after some sequence of relaxations, then Gπ is a shortest-paths tree rooted at s.

Proof:

1. V' = reachable vertices: v has finite d iff v is reachable from s
2. Tree structure: Follows from Lemma 24.16
3. Shortest paths: For the unique path p from s to v in Gπ, summing w(vᵢ₋₁, vᵢ) ≤ δ(s, vᵢ) − δ(s, vᵢ₋₁) telescopes to w(p) ≤ δ(s, v). Since δ(s, v) is a lower bound, w(p) = δ(s, v).

---

Summary Comparison