All-Pairs Shortest Paths — Floyd-Warshall, Johnson’s Algorithm & Matrix Methods | Chapter 23 in Introduction to Algorithms

Chapter 23 of Introduction to Algorithms (CLRS) dives into solving one of the most fundamental problems in graph theory: the all-pairs shortest paths (APSP) problem. This chapter introduces several algorithmic strategies—ranging from matrix multiplication using the tropical semiring to the efficient Floyd-Warshall and Johnson’s algorithms—that compute shortest path distances between every pair of vertices in a weighted, directed graph. These methods are widely applicable in routing, scheduling, reachability analysis, and computational optimization.

📺 Watch the full video above for a comprehensive summary, or continue reading for a detailed, searchable guide to every major algorithm and concept in Chapter 23.

What Is the All-Pairs Shortest Paths Problem?

The APSP problem aims to compute the shortest paths between all pairs of vertices in a graph. The result is typically represented as a distance matrix D[i][j] containing the shortest path weights from vertex i to vertex j. A companion predecessor matrix may also be maintained for reconstructing paths.

• Applications: Network routing, scheduling, graph diameter computation, and transitive closure.
• Choice of algorithm: Floyd-Warshall is optimal for dense graphs, while Johnson’s algorithm is preferred for sparse graphs.

Naive Approach: Repeated Single-Source Algorithms

One basic strategy is to run a single-source shortest path algorithm (like Dijkstra or Bellman-Ford) from each vertex:

• Dijkstra (nonnegative weights): O(V² log V + VE)
• Bellman-Ford (handles negatives): O(V²E) — too slow for dense graphs

Although conceptually simple, this approach becomes inefficient on large or dense graphs.

Matrix-Based Methods & the Tropical Semiring

This elegant method treats the APSP problem as a form of matrix multiplication using the tropical semiring:

• Addition → min, Multiplication → +
• Identity element = 0; absorbing element = ∞
• lᵢⱼ^(r) = shortest path weight from i to j using ≤ r edges

Two matrix algorithms are based on this framework:

• SLOW-APSP: Θ(n⁴) using n–1 matrix multiplications
• FASTER-APSP: Θ(n³ log n) using repeated squaring

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming solution that builds up shortest paths by considering intermediate vertices:

• dᵢⱼ^(k) = min(dᵢⱼ^(k–1), dᵢₖ^(k–1) + dₖⱼ^(k–1))
• Time complexity: Θ(n³)
• Space complexity: Θ(n²)

The algorithm can also build a predecessor matrix (πᵢⱼ) to reconstruct shortest paths using a recursive procedure like PRINT-ALL-PAIRS-SHORTEST-PATH.

Transitive Closure

Floyd-Warshall can be adapted for transitive closure to determine reachability between all pairs of vertices:

• Replace weight values with Boolean logic
• min → OR, + → AND
• Time complexity: Θ(n³)

Additionally, the algorithm can detect negative-weight cycles if any dᵢᵢ becomes negative.

Johnson’s Algorithm for Sparse Graphs

Johnson’s algorithm is an advanced solution tailored for sparse graphs and graphs with negative weights (but no negative cycles). It cleverly reweights edges to enable the use of Dijkstra’s algorithm:

1. Add new node s with zero-weight edges to all nodes.
2. Run Bellman-Ford from s to compute potential values h(v).
3. Reweight edge (u, v): ŵ(u, v) = w(u, v) + h(u) – h(v)
4. Run Dijkstra’s algorithm from each vertex using reweighted graph.
5. Recover original distances: δ(u, v) = δ̂(u, v) + h(v) – h(u)

• Time complexity: O(V² log V + VE)

Glossary of Key Terms

• All-Pairs Shortest Paths (APSP): Compute shortest paths between every pair of vertices.
• Tropical Semiring: Algebra where addition = min and multiplication = +.
• Floyd-Warshall: Dynamic programming APSP algorithm with Θ(n³) runtime.
• Transitive Closure: Boolean matrix showing reachability across all pairs.
• Predecessor Matrix: Tracks previous nodes on shortest paths.
• Repeated Squaring: Speeds up matrix exponentiation.
• Reweighting: Edge transformation that maintains shortest paths while eliminating negatives.
• Johnson’s Algorithm: Efficient APSP method for sparse graphs using reweighting + Dijkstra.

Conclusion

Chapter 23 presents a diverse toolkit for tackling the all-pairs shortest paths problem across different graph types. Whether using matrix operations, dynamic programming, or reweighting strategies, these algorithms form the backbone of complex systems in logistics, networking, and computation. Understanding when to apply each method—and how they connect—deepens your grasp of both algorithm design and real-world optimization challenges.

🎓 Watch the complete breakdown in video format here: All-Pairs Shortest Paths — CLRS Chapter 23.

📘 To explore more topics from Introduction to Algorithms, visit the Last Minute Lecture YouTube channel for additional summaries.

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.