Whenever I’ve needed to know the shortest distance between every single pair of nodes in a graph — not just from one starting point, but from all of them to all of them at once — I’ve turned to the Floyd-Warshall algorithm. What draws me to it is its almost deceptive simplicity: a triple-nested loop and one line of comparison inside, yet it solves what seems like it should be a much harder problem. It’s an all-pairs shortest path algorithm, and I find it especially elegant because of how directly the code mirrors the underlying dynamic programming idea, with almost no extra machinery needed.
History and Background
I attribute this algorithm to Robert Floyd, who published it in 1962, building on a related but more general result by Stephen Warshall, who in 1962 had already published an algorithm (Warshall’s algorithm) for computing the transitive closure of a relation. Floyd essentially adapted Warshall’s approach to compute shortest path distances instead of just reachability, which is why the combined method is credited to both names. Interestingly, the same core dynamic programming idea had also been described earlier by Bernard Roy in 1959, so it is occasionally referred to as the Roy-Floyd-Warshall algorithm in some literature, particularly outside the English-speaking world.
Problem Statement
I want to compute the shortest path distance between every pair of vertices in a weighted, directed graph, where edge weights can be negative, but the graph must not contain a negative-weight cycle (a cycle would allow paths to have arbitrarily low cost, making “shortest path” undefined). Running a single-source shortest path algorithm like Dijkstra or Bellman-Ford from every vertex individually would work, but at a higher combined cost in many cases. Floyd-Warshall solves the all-pairs version directly using dynamic programming over intermediate vertices, in a way that’s often simpler to implement than repeating a single-source algorithm many times, especially when the graph is dense.
Core Concepts
- Adjacency matrix: I represent the graph as a matrix
dist[i][j], initialized to the direct edge weight fromitoj(or infinity if no edge exists, and0ifi == j). - Intermediate vertex: a vertex
kthat a path fromitojmight pass through. - Dynamic programming state:
dist_k[i][j]represents the shortest path fromitojusing only vertices{1, ..., k}as allowed intermediate stops. - Negative cycle: a cycle whose total edge weight sums to a negative number, which invalidates the concept of a shortest path for any pair of vertices reachable through it.
- Path reconstruction matrix: an auxiliary structure (
next[i][j]) used to recover the actual shortest path, not just its length.
How It Works
I proceed by considering, one at a time, whether allowing a new vertex k as an intermediate stop improves any existing shortest path estimate. Concretely:
- I initialize
dist[i][j]with direct edge weights (or infinity if there’s no direct edge), anddist[i][i] = 0. - For each vertex
kfrom1ton(used as a potential intermediate stop), I check for every pair(i, j)whether going throughk— i.e.,dist[i][k] + dist[k][j]— is shorter than the currently knowndist[i][j]. - If it is, I update
dist[i][j]to this shorter value. - After considering all vertices
kas potential intermediates,dist[i][j]holds the true shortest path distance between every pair(i, j). - Optionally, I also check the diagonal
dist[i][i]for negative values after the algorithm finishes, which indicates the presence of a negative cycle.
Working Principle
The core mechanism is a very specific form of dynamic programming where I gradually expand the set of vertices allowed as intermediate stops. At each stage k, I’ve already correctly computed the shortest paths using only vertices {1, ..., k-1} as allowed intermediates. Adding vertex k to the allowed set can only help (never hurt), because I always compare the new candidate path against the old value and keep whichever is smaller. This staged expansion guarantees that by the time k reaches n (all vertices considered), every possible intermediate combination has been accounted for, giving the true shortest path over the entire graph.
Mathematical Foundation
I define the DP relation as:
$$ dist_k[i][j] = \min\big(dist_{k-1}[i][j],\ dist_{k-1}[i][k] + dist_{k-1}[k][j]\big) $$
with the base case:
$$ dist_0[i][j] = \begin{cases} 0 & \text{if } i = j \ w(i,j) & \text{if there is an edge from } i \text{ to } j \ \infty & \text{otherwise} \end{cases} $$
After considering all n vertices as intermediates, dist_n[i][j] gives the true shortest path distance between i and j. The total time complexity follows directly from the three nested loops over k, i, and j, each ranging over all n vertices:
$$ T(n) = O(n^3) $$
Diagrams
flowchart TD
A["Initialize dist matrix with direct edge weights, infinity elsewhere, 0 on diagonal"] --> B["for k = 1 to n"]
B --> C["for i = 1 to n"]
C --> D["for j = 1 to n"]
D --> E{"dist[i][k] + dist[k][j] < dist[i][j]?"}
E -- Yes --> F["dist[i][j] = dist[i][k] + dist[k][j]"]
E -- No --> G[Keep current value]
F --> H{More j?}
G --> H
H -- Yes --> D
H -- No --> I{More i?}
I -- Yes --> C
I -- No --> J{More k?}
J -- Yes --> B
J -- No --> K["dist matrix now holds all-pairs shortest paths"]Pseudocode
function floydWarshall(graph, n):
dist = new n x n matrix
for i from 1 to n:
for j from 1 to n:
if i == j:
dist[i][j] = 0
else if edge (i, j) exists:
dist[i][j] = weight(i, j)
else:
dist[i][j] = infinity
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
for i from 1 to n:
if dist[i][i] < 0:
return "Negative cycle detected"
return dist
Step-by-Step Example
Consider a 4-node graph (A, B, C, D) with directed edges: A->B (3), A->C (8), B->C (2), C->D (1), B->D (7).
Initial dist matrix (using ∞ for no direct edge):
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 3 | 8 | ∞ |
| B | ∞ | 0 | 2 | 7 |
| C | ∞ | ∞ | 0 | 1 |
| D | ∞ | ∞ | ∞ | 0 |
After considering k = B: dist[A][C] can be updated via A -> B -> C = 3 + 2 = 5, which is better than the direct 8. Also dist[A][D] via A -> B -> D = 3 + 7 = 10.
After considering k = C: dist[A][D] can be updated via A -> C -> D. Using the already-improved dist[A][C] = 5, this gives 5 + 1 = 6, better than the previous 10. Also dist[B][D] via B -> C -> D = 2 + 1 = 3, better than the direct 7.
Final dist matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 3 | 5 | 6 |
| B | ∞ | 0 | 2 | 3 |
| C | ∞ | ∞ | 0 | 1 |
| D | ∞ | ∞ | ∞ | 0 |
Time Complexity
- Best case:
O(n^3)— the algorithm always runs the full triple loop regardless of graph structure or density. - Average case:
O(n^3). - Worst case:
O(n^3)— this is both a strength (predictable performance) and a weakness (no way to finish early on sparse or simple graphs).
Space Complexity
The algorithm requires O(n^2) space to store the distance matrix. If I also want to reconstruct actual shortest paths (not just distances), I need an additional O(n^2) space for the next (successor) matrix used in path reconstruction. The algorithm can be implemented in-place, updating the same matrix throughout, without needing separate matrices for each value of k.
Correctness Analysis
I prove correctness by induction on k, the number of intermediate vertices considered so far. The base case (k = 0) is trivially correct, since dist_0[i][j] is defined directly from the input graph with no intermediates allowed. For the inductive step, I assume dist_{k-1}[i][j] correctly holds the shortest path using only vertices {1, ..., k-1} as intermediates. When considering vertex k, any shortest path from i to j using vertices {1, ..., k} either doesn’t use k at all (in which case its length is already captured by dist_{k-1}[i][j]), or it uses k exactly once as an intermediate stop (since a shortest path never revisits a vertex, assuming no negative cycles), splitting into a path from i to k and from k to j, each of which only uses vertices {1, ..., k-1} as further intermediates by definition. Taking the minimum of these two cases, as the recurrence does, therefore correctly computes dist_k[i][j]. By induction, dist_n[i][j] is correct for all pairs after considering all n vertices.
Advantages
- Computes shortest paths between all pairs of vertices in a single run, which is often simpler to implement than running a single-source algorithm
ntimes. - Naturally handles negative edge weights, unlike Dijkstra’s algorithm.
- Can detect negative cycles by checking for negative values on the diagonal after completion.
- The implementation is remarkably compact — just three nested loops — making it easy to code correctly under time pressure, such as in a contest setting.
Disadvantages
- Cubic time complexity
O(n^3)makes it impractical for very large graphs (say, tens of thousands of vertices or more). - Uses
O(n^2)space, which can also become a bottleneck for very large graphs. - Doesn’t scale as well as running Dijkstra’s algorithm from every vertex when the graph is sparse and has no negative weights, since sparse-graph Dijkstra with a good heap implementation can outperform Floyd-Warshall’s dense cubic cost.
- Doesn’t directly give path reconstruction without maintaining an auxiliary matrix.
Applications
- Network routing protocols that need to precompute shortest paths between all router pairs.
- Computing the transitive closure of relations (a direct generalization, replacing min/plus operations with logical OR/AND).
- Game development, for precomputing distances between all points on a game map for AI pathfinding.
- Traffic and logistics systems needing shortest travel times or distances between all pairs of locations in a city or delivery network.
- Detecting arbitrage opportunities in currency exchange graphs, using a variant that checks for negative cycles (which correspond to profitable arbitrage loops).
Implementation in C
#include <stdio.h>
#include <limits.h>
#define V 4
#define INF INT_MAX / 2 /* avoid overflow when adding two "infinities" */
void floydWarshall(int graph[V][V]) {
int dist[V][V];
/* Initialize distance matrix same as input graph */
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Try every vertex k as an intermediate point */
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
/* Check for negative cycles */
for (int i = 0; i < V; i++) {
if (dist[i][i] < 0) {
printf("Graph contains a negative weight cycle.\n");
return;
}
}
printf("Shortest distances between every pair of vertices:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main() {
/* 0=A, 1=B, 2=C, 3=D */
int graph[V][V] = {
{0, 3, 8, INF},
{INF, 0, 2, 7},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}
Sample Input and Output
Input: the 4-node graph A, B, C, D with edges A->B(3), A->C(8), B->C(2), C->D(1), B->D(7).
Output:
Shortest distances between every pair of vertices:
0 3 5 6
INF 0 2 3
INF INF 0 1
INF INF INF 0
Optimization Techniques
- Bitset optimization for transitive closure: when only reachability (not distance) matters, using bitsets for each row allows the innermost loop to be vectorized, often via built-in word-level operations, greatly speeding up practical performance.
- Blocked/tiled matrix computation: reorganizing the triple loop to operate on cache-friendly blocks of the matrix can improve real-world performance significantly due to better cache locality, even though the asymptotic complexity remains
O(n^3). - Early negative cycle detection: checking the diagonal for negative values as soon as it appears, rather than waiting until the full algorithm finishes, can save time in graphs known to potentially have negative cycles.
- Parallelization: since each
(i,j)update within a fixedkis independent of others in the same iteration, the inner double loop can be parallelized across multiple cores or GPU threads.
Common Mistakes
- Iterating
iandjin the outer loops andkin the innermost loop — the order must bekoutermost,iandjinside, or the dynamic programming invariant breaks and the algorithm produces incorrect results. - Using a naive “infinity” value like
INT_MAXdirectly, which can cause integer overflow when added to another large number; a safer convention is to useINT_MAX / 2or a similarly scaled sentinel value. - Forgetting to initialize
dist[i][i] = 0, which can cause incorrect self-distances, especially in graphs with self-loops of negative weight. - Applying Floyd-Warshall to graphs with negative cycles without checking for them afterward, which silently produces meaningless (arbitrarily decreasing) results for affected pairs.
Further Reading
- Floyd, R. W. “Algorithm 97: Shortest Path,” Communications of the ACM, 1962: https://dl.acm.org/doi/10.1145/367766.368168
- Warshall, S. “A Theorem on Boolean Matrices,” Journal of the ACM, 1962: https://dl.acm.org/doi/10.1145/321105.321107
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. “Introduction to Algorithms” (CLRS), Chapter on All-Pairs Shortest Paths: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “Floyd Warshall Algorithm”: https://www.geeksforgeeks.org/dsa/floyd-warshall-algorithm-dp-16/
- Wikipedia, “Floyd–Warshall algorithm”: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
