Shortest Path Problems in Weighted Graphs
A systematic treatment of shortest path algorithms: BFS for unweighted graphs, Dijkstra's algorithm with a correctness proof, the Bellman--Ford algorithm with negative-cycle detection, the Floyd--Warshall algorithm, and shortest paths in DAGs.
1 Formulation of the Shortest Path Problem
Definition 1 (Weighted graph and path weight).
A weighted graph consists of a graph together with a weight function . The weight (or length) of a path is
Definition 2 (Shortest path and shortest distance).
Let denote the set of all paths from to . The shortest distance is
A path with is called a shortest path.
Remark 3.
If a cycle of negative total weight (a negative cycle) is reachable, one can traverse it arbitrarily many times to make the path weight arbitrarily small, so no shortest path exists. We encode this situation as .
2 BFS Shortest Paths: The Unweighted Case
When every edge has weight , BFS (breadth-first search) correctly computes shortest distances.
Theorem 4 (Correctness of BFS).
In an unweighted graph , run BFS from a source and let be the layer at which is discovered. Then for every .
Proof.
We proceed by induction on . For we have and . Suppose and that the claim holds for all vertices at distance at most . Let be a shortest path. By induction, . When BFS processes , it enqueues (if not already visited), so . On the other hand, would imply (since BFS traverses each edge in one step), a contradiction. Hence . □
The running time of BFS is .
Algorithm 1: Breadth-First Search (BFS)
Input:
Graph , source Output:
Shortest distances for all
end for
Queue
Enqueue()
while
for all
if
Enqueue()
end if
end for
end while
return
3 Dijkstra's Algorithm
When all edge weights are nonnegative, Dijkstra's algorithm efficiently solves the single-source shortest path problem. The algorithm maintains a set of vertices whose shortest distances have been finalized. At each step, it selects the vertex with the smallest tentative distance , adds to , and relaxes the edges leaving .
Definition 5 (Relaxation).
Relaxation of an edge is the operation: if , update .
Theorem 6 (Correctness of Dijkstra's algorithm).
When all edge weights are nonnegative, Dijkstra's algorithm correctly computes for every vertex .
Proof.
We show by induction on the order in which vertices are added to that at the moment is added.Base case. The source is added first with .Inductive step. Let be the next vertex added to , and suppose for contradiction that . Consider a shortest path from to . Let be the first edge on with and . By induction, . When was added to , the edge was relaxed, so
Since and precedes on , we have . Thus . But was chosen as the vertex outside with the smallest -value, so — a contradiction. □
Algorithm 2: Dijkstra's Algorithm
Input:
Graph , nonnegative weights , source Output:
Shortest distances for all
end for
Insert all vertices into priority queue with key
while
for all
if
DecreaseKey()
end if
end for
end while
return
Remark 7.
With a binary heap, the running time is . With a Fibonacci heap, it improves to .
4 The Bellman–Ford Algorithm
When edges may have negative weights, Dijkstra's algorithm fails. The Bellman–Ford algorithm handles negative weights and can also detect negative cycles. It works by relaxing all edges times.
Theorem 8 (Correctness of Bellman–Ford).
If no negative cycle is reachable from , then after iterations, for every vertex .
Proof.
In the absence of negative cycles, every shortest path has at most edges. Let (with ) be a shortest path from to . We claim that after iteration , . For , . Assuming the claim for : after iteration , . In iteration , the edge is relaxed, giving
Since always holds (relaxation never makes smaller than the true distance), equality follows. □
Theorem 9 (Negative cycle detection).
After iterations, perform one additional pass over all edges. If any is updated, then a negative cycle reachable from exists.
Proof.
If no negative cycle exists, all -values are finalized after iterations and no update occurs in the extra pass. By contrapositive, an update implies a negative cycle. □
The running time of Bellman–Ford is .
Algorithm 3: Bellman–Ford Algorithm
Input:
Directed graph , weights , source Output:
Shortest distances , negative cycle detection for all
end for
for to
for all
if
end if
end for
end for
// Negative cycle detection
for all
if
return "Negative cycle exists"
end if
end for
return
5 The Floyd–Warshall Algorithm
The Floyd–Warshall algorithm computes shortest distances between all pairs of vertices using dynamic programming.
Theorem 10 (Floyd–Warshall recurrence).
Let , and let be the weight of a shortest path from to using only vertices in as intermediaries. Then
and .
Proof.
A shortest path from to that avoids vertex as an intermediate has weight . A shortest path that does pass through decomposes as ; in the absence of negative cycles, appears at most once, so its weight is . The minimum of these two cases gives . □
Algorithm 4: Floyd–Warshall Algorithm
Input:
Directed graph , weights , Output:
All-pairs shortest distances for to
for to
if
else if
else
end if
end for
end for
for to
for to
for to
end for
end for
end for
return
The running time is . A negative cycle through vertex is detected when .
6 Shortest Paths in DAGs
Theorem 11 (Linear-time shortest paths in DAGs).
In a DAG (directed acyclic graph), single-source shortest paths can be computed in time by processing vertices in topological order and relaxing each edge exactly once.
Proof.
In a topological ordering, whenever an edge exists, appears before . Therefore, by the time vertex is processed, every edge entering has already been relaxed with the correct value . The relaxation of then yields . □
Remark 12.
This method works correctly even with negative edge weights, since a DAG has no cycles and hence no negative cycles. It is widely applied in project scheduling: computing the longest path (critical path) in a DAG is the basis of PERT (Program Evaluation and Review Technique).
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 followers·105 articles