Chapter 22: Single-Source Shortest Paths: Bellman-Ford and Dijkstra's Algorithm

Two foundational principles underpin all algorithms in the chapter: optimal substructure, meaning any subpath of a shortest path is itself a shortest path, and relaxation, the process of improving a vertex's distance estimate v.d by checking whether a known edge offers a better route, with a predecessor pointer v.π tracking the current best-known path — noting that negative-weight edges are permitted but negative cycles render shortest paths undefined. The Bellman-Ford algorithm handles the most general case by relaxing all edges V–1 times and performing a final pass to detect negative-weight cycles, returning FALSE if one exists and running in O(V × E) time, making it suitable for routing protocols and difference constraint systems. For directed acyclic graphs, the DAG shortest-paths algorithm achieves the optimal Θ(V + E) time by first topologically sorting vertices and then relaxing edges in that order, making it ideal for critical path analysis in scheduling. Dijkstra's algorithm handles graphs with nonnegative edge weights by maintaining a min-priority queue of unfinalized vertices, repeatedly extracting the vertex with the smallest estimate and relaxing its outgoing edges — achieving O(V² + E) with an array, O((V + E) log V) with a binary heap, and the superior O(V log V + E) with a Fibonacci heap, structurally mirroring Prim's MST algorithm. The chapter also demonstrates how systems of difference constraints — inequalities of the form xⱼ – xᵢ ≤ bₖ — can be modeled as a graph and solved with Bellman-Ford, and closes with formal proofs of the triangle inequality, upper-bound, convergence, and path-relaxation properties that collectively guarantee the correctness and termination of all algorithms presented.