Shortest Path Algorithms — Bellman-Ford, Dijkstra & DAG Methods Explained | Chapter 22 in Introduction to Algorithms

Chapter 22 of Introduction to Algorithms (CLRS) provides a comprehensive guide to solving the single-source shortest-path problem in weighted, directed graphs. These algorithms are the foundation of many practical applications in computer science, such as GPS navigation, internet routing, and task scheduling. The chapter introduces essential algorithmic tools—including relaxation and optimal substructure—before explaining three powerful solutions: the Bellman-Ford algorithm, DAG shortest paths, and Dijkstra’s algorithm.

📺 Watch the full podcast-style summary above or continue reading for a detailed breakdown of key concepts, methods, and properties that make shortest-path algorithms so essential in graph theory.

Understanding the Shortest Path Problem

The single-source shortest path problem asks: given a weighted, directed graph and a source vertex s, what is the minimum-cost path from s to each other vertex? This chapter focuses on the single-source case, with applications ranging from navigation systems to dependency analysis.

• Single-destination: Reverse edges to reduce to single-source.
• Single-pair: Solve for one source or destination.
• All-pairs: Covered in Chapter 23.

Core Concepts: Relaxation & Optimal Substructure

Before diving into specific algorithms, Chapter 22 introduces key properties that underpin all shortest-path solutions:

• Optimal Substructure: Any subpath of a shortest path is itself a shortest path.
• Relaxation: Iteratively improves path estimates by checking if known paths can be shortened.
• Shortest-path estimate (v.d): Upper bound on the cost to reach vertex v.
• Predecessor (v.pi): Points to the previous vertex on the current best-known path.

Bellman-Ford Algorithm

Bellman-Ford is a versatile algorithm capable of handling graphs with negative-weight edges—something Dijkstra’s algorithm cannot do. It repeatedly relaxes all edges and detects negative-weight cycles.

• Performs V - 1 passes over all edges.
• Final pass checks for negative-weight cycles.
• Returns FALSE if a negative cycle exists; otherwise, returns TRUE.
• Time complexity: O(V × E)
• Applications: Used in routing protocols and solving difference constraints.

DAG Shortest Paths

In directed acyclic graphs (DAGs), shortest paths can be found more efficiently through topological sorting:

• Perform a topological sort of all vertices.
• Relax each edge in order of sorted vertices.
• Time complexity: Θ(V + E)
• Ideal for task scheduling and project management (e.g., critical path analysis).

Dijkstra’s Algorithm

Dijkstra’s algorithm efficiently solves the shortest-path problem in graphs with nonnegative edge weights. It shares structural similarities with Prim’s MST algorithm.

• Maintains set S of vertices with known shortest paths.
• Uses a min-priority queue Q to extract the minimum-distance vertex.
• Relaxes edges from the extracted node to update neighbors.
• Time complexities:
  • Array-based queue: O(V² + E)
  • Binary heap: O((V + E) log V)
  • Fibonacci heap: O(V log V + E)

Difference Constraints and Graphs

Difference constraints appear as inequalities of the form xj - xi ≤ bk and can be represented as weighted graphs. To solve them:

• Each constraint becomes a directed edge.
• Add new node v₀ with zero-weight edges to all other vertices.
• Run Bellman-Ford from v₀ to compute shortest-path estimates.
• Feasibility: No negative-weight cycles implies a valid solution.
• Time complexity: O(n × m) for n variables and m constraints.

Algorithmic Properties and Proofs

To close, the chapter rigorously proves several essential properties that guarantee correctness:

• Triangle Inequality: Direct path ≤ any alternative route.
• Upper-Bound Property: Relaxation never underestimates the true shortest path.
• Convergence Property: Estimates converge to the true value after correct relaxations.
• Path-Relaxation Property: Relaxing edges in a shortest path order yields correct distances.

Glossary of Key Terms

• Weighted Directed Graph: Graph with directional edges and weights.
• Relaxation: Updating a shortest-path estimate based on better known values.
• Shortest-Path Estimate (v.d): The current best-known cost from the source.
• Negative-Weight Edge: An edge with a negative value, allowed by Bellman-Ford.
• Negative-Weight Cycle: A cycle with a total negative weight—makes shortest paths undefined.
• Topological Sort: Ordering of vertices where every directed edge u → v ensures u comes before v.
• Min-Priority Queue: Structure used to extract the smallest estimate quickly.
• Difference Constraint: Inequality constraint modeled using graph edges.
• Shortest-Paths Tree: Subgraph showing the best known paths from a source.

Conclusion

Whether you're routing internet traffic or building a project schedule, shortest path algorithms are indispensable tools in algorithmic design. Bellman-Ford provides flexibility for negative weights, Dijkstra’s ensures fast performance with nonnegative graphs, and DAG methods give elegant solutions for acyclic structures. Understanding these tools—and the theory that proves them—is foundational for advanced study in computer science.

🎓 Dive deeper by watching the full chapter summary on YouTube.

📘 Continue learning with more episodes from Introduction to Algorithms on the Last Minute Lecture channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.