The All-Pairs Shortest Paths Problem
The single-source algorithms discussed earlier in this series, Bellman-Ford and Dijkstra's algorithm, find shortest paths from one specific source vertex to every other vertex. The All-Pairs Shortest Paths problem asks for something more comprehensive: the shortest distance between every possible ordered pair of vertices in the graph.
A Naive Approach: Running Dijkstra Repeatedly
The most obvious solution runs a single-source algorithm once from each vertex as the source. Using Dijkstra's algorithm, discussed earlier in this series, for each of the V vertices as a source gives a total running time of O(V · (E + V log V)) when using a Fibonacci heap, which simplifies to O(V² log V + VE). This works well for graphs without negative weights, but if negative weights are present, Dijkstra's algorithm cannot be used, and running Bellman-Ford from every source instead gives O(V²E), which becomes O(V⁴) for dense graphs — quite slow.
The Floyd-Warshall Algorithm: A Direct Dynamic Programming Approach
Rather than repeatedly running a single-source algorithm, Floyd-Warshall solves the all-pairs problem directly using dynamic programming, discussed earlier in this series, and correctly handles negative edge weights, though not negative cycles.
Defining the Subproblem
The key insight is to consider paths restricted by which intermediate vertices they are allowed to pass through. Define d_{ij}^{(k)} as the shortest distance from vertex i to vertex j, using only vertices from {1, 2, ..., k} as possible intermediate stops along the path.
d_{ij}^{(0)} = w(i, j) if an edge (i,j) exists
= infinity otherwise
= 0 if i == j
For k ≥ 1, the recursive relationship considers
whether the optimal path uses vertex k as an
intermediate stop or not:
d_{ij}^{(k)} = min(
d_{ij}^{(k-1)}, // don't use vertex k
d_{ik}^{(k-1)} + d_{kj}^{(k-1)} // do use vertex k
)This recurrence says: the shortest path from i to j allowed to use vertices up to k either does not actually use vertex k at all (in which case it equals the shortest path restricted to vertices up to k-1), or it does pass through vertex k exactly once (in which case it splits into the shortest path from i to k, plus the shortest path from k to j, both restricted to intermediate vertices up to k-1).
Implementing the Algorithm
FLOYD-WARSHALL(W, n):
D⁽⁰⁾ = W // initialize with direct edge weights
for k = 1 to n:
let D⁽ᵏ⁾ be a new n × n matrix
for i = 1 to n:
for j = 1 to n:
D⁽ᵏ⁾[i][j] = min(D⁽ᵏ⁻¹⁾[i][j],
D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j])
return D⁽ⁿ⁾In practice, this is implemented using a single matrix updated in place, since each entry only depends on values from the current or previous iteration in a way that permits this simplification without affecting correctness.
Tracing a Small Example
Initial weight matrix (∞ means no direct edge):
1 2 3
1 [ 0 3 ∞ ]
2 [ ∞ 0 1 ]
3 [ 2 ∞ 0 ]
After considering vertex 1 as an intermediate:
(check if going through 1 improves any pair)
3→2 via 1: 3[1] + 1[2] = 2 + 3 = 5, but current is ∞, so update
After considering vertex 2 as an intermediate:
1→3 via 2: 1[2] + 2[3] = 3 + 1 = 4, current is ∞, so update
After considering vertex 3 as an intermediate:
2→1 via 3: 2[3] + 3[1] = 1 + 2 = 3, current is ∞, so update
Final matrix contains the shortest path between every pairAnalyzing the Running Time
The algorithm consists of three nested loops, each running n times, with O(1) work inside the innermost loop, giving a total running time of Θ(V³). This is remarkably simple to implement — just three nested loops with a single comparison — and does not depend on any complex data structure like the priority queues required by Dijkstra's algorithm.
Comparing Floyd-Warshall Against Repeated Single-Source Runs
Floyd-Warshall: Θ(V³), always, handles negative weights
Repeated Dijkstra: O(V² log V + VE), faster for sparse
graphs, but cannot handle negative weights
Repeated Bellman-Ford: O(V²E), which becomes O(V⁴) for dense
graphs, handles negative weights but slower
than Floyd-Warshall for dense graphsFor dense graphs (where E is close to V²), Floyd-Warshall's Θ(V³) is comparable to or better than the alternatives, and its simplicity of implementation, along with correct handling of negative weights without needing the more complex Bellman-Ford repeated V times, makes it the practical choice whenever the graph is not extremely sparse.
Detecting Negative Cycles with Floyd-Warshall
Similar to how Bellman-Ford, discussed earlier in this series, detects negative cycles by checking for further improvement after its main loop finishes, Floyd-Warshall detects a negative-weight cycle by checking the diagonal of the final distance matrix: if any D[i][i] is negative after the algorithm completes, this means there exists a path from vertex i back to itself with negative total weight — a negative cycle passing through i.
Reconstructing Actual Paths
Similar to the predecessor tracking used in single-source algorithms discussed earlier in this series, Floyd-Warshall can maintain a companion matrix of predecessors, updated alongside the distance matrix at every step, allowing the actual shortest path between any pair of vertices, not just its length, to be reconstructed afterward.
Why Floyd-Warshall's Simplicity Is a Genuine Strength
Beyond its competitive running time for dense graphs, Floyd-Warshall's implementation simplicity — a direct triple-nested loop with no auxiliary data structures — makes it far less error-prone to implement correctly compared to running a priority-queue-based algorithm repeatedly from every source. This is part of why Floyd-Warshall remains a standard tool for all-pairs shortest path problems in practice, particularly for moderately sized dense graphs where its cubic running time remains entirely practical.