The Floyd-Warshall algorithm computes the shortest path between every pair of vertices in a weighted directed graph in a single run. Dijkstra and Bellman-Ford solve the single-source variant, finding shortest paths from one fixed vertex; Floyd-Warshall solves the all-pairs variant, producing a full V x V distance matrix. It is a dynamic programming algorithm that runs in O(V^3) and fits into about 10 lines of code.

This chapter covers how the algorithm works, why it works, how to detect negative cycles, how to reconstruct actual paths, and when to use Floyd-Warshall versus alternatives like Dijkstra or Bellman-Ford.

The result is a V x V distance matrix where entry dist[i][j] holds the shortest path length from vertex i to vertex j.

Its main properties:

Floyd-Warshall is named after Robert Floyd and Stephen Warshall, who independently published related algorithms in 1962. Warshall's version solved transitive closure (reachability), while Floyd's version handled shortest paths.

The core insight behind Floyd-Warshall is this. For every pair of vertices (i, j), ask this question:

If yes, update the shortest distance. If not, leave it alone.

The formula is:

The algorithm tries every possible intermediate vertex k, one at a time. After considering all V vertices as potential intermediates, the distance matrix contains the true shortest paths.

Why This Works

The shortest path from vertex i to vertex j either:

By iterating k over all vertices, the algorithm exhaustively checks every possible "shortcut" through the graph. The dynamic programming structure guarantees that by the time vertex k is considered as an intermediate, the optimal distances using only vertices {0, 1, ..., k-1} as intermediates are already computed.

Consider three vertices where the direct path from A to C costs 10, but going through B costs 3 + 4 = 7.

When the algorithm considers B as an intermediate vertex, it finds that dist[A][B] + dist[B][C] = 3 + 4 = 7 < 10 = dist[A][C], so it updates dist[A][C] to 7.

The complete Floyd-Warshall implementation:

Initialization

The input graph is a V x V adjacency matrix where:

This is copied into a dist matrix. As the algorithm runs, dist[i][j] gradually converges to the true shortest path.

Why k Must Be the Outer Loop

The loop order is k (outer), i (middle), j (inner), and the k loop must be outermost.

The dynamic programming state is defined as: dist_k[i][j] = shortest path from i to j using only vertices {0, 1, ..., k} as intermediates. Computing dist_k[i][j] requires dist_{k-1}[i][k] and dist_{k-1}[k][j], which means all updates for intermediate vertices 0 through k-1 must already be complete.

Putting i or j as the outer loop would update distances for different intermediates in a jumbled order, and the DP recurrence breaks. The k-outer order is what makes the DP correct.

Why In-Place Update Works

The DP formulation defines two layers: dist_{k-1} (the previous layer) and dist_k (the new layer being computed). A textbook implementation would keep both matrices and write into a fresh dist_k. The code above uses a single dist matrix and overwrites in place, and the in-place update produces exactly the same values.

The reason is that the two source values dist[i][k] and dist[k][j] do not change during iteration k. Consider what happens during their updates:

Because the k-th row and k-th column are stable during iteration k, reading them in place is identical to reading them from a separate dist_{k-1} matrix. This saves a full V x V matrix of memory at no cost to correctness. The argument relies on dist[k][k] = 0, which is why the initialization step matters.

Why Not Use the Language's Max Integer for INF?

The code uses 100000000 (10^8) instead of the maximum integer constant (such as Integer.MAX_VALUE in Java, INT_MAX in C++, or int.MaxValue in C#). This is deliberate. When the algorithm computes dist[i][k] + dist[k][j], if both values are the max integer, the addition overflows to a negative number. That negative result would incorrectly "win" the min comparison and corrupt the distance matrix.

Using a large but safe value avoids this trap entirely. Choose a value large enough that no real shortest path would reach it, but small enough that adding two of them does not overflow.

Here is a trace of Floyd-Warshall on a small graph with 4 vertices (0, 1, 2, 3).

Edges: (0->1, weight 3), (0->2, weight 7), (1->2, weight 2), (1->3, weight 5), (2->3, weight 1), (3->0, weight 2).

Initial Distance Matrix

Fill the matrix with direct edge weights. Missing edges get INF, and the diagonal is 0.

k = 0 (Intermediate vertex: 0)

For each pair (i, j), check if going through vertex 0 improves the path.

k = 1 (Intermediate vertex: 1)

k = 2 (Intermediate vertex: 2)

k = 3 (Intermediate vertex: 3)

Final Distance Matrix:

Every cell now contains the shortest distance between that pair of vertices. For example, the shortest path from vertex 1 to vertex 0 is 5 (going 1->3->0, with cost 3 + 2).

Floyd-Warshall handles negative edge weights correctly. The trouble starts when there is a negative cycle, a cycle whose total weight is negative. If such a cycle exists, the concept of "shortest path" becomes meaningless, since looping around the cycle indefinitely reduces the distance without bound.

After running the algorithm, check the diagonal of the distance matrix. If dist[i][i] < 0 for any vertex i, then vertex i lies on a negative cycle.

Why? The value dist[i][i] represents the shortest "path" from vertex i back to itself. Normally that is 0 (the empty path). But if there is a negative cycle reachable from i that loops back to i, the algorithm will find that going around the cycle gives a cost less than 0.

In the graph above, the cycle A -> B -> C -> A has total weight 2 + (-5) + 1 = -2. After Floyd-Warshall runs, dist[A][A], dist[B][B], and dist[C][C] will all be negative, signaling that each of these vertices is part of a negative cycle.

Knowing the shortest distance is useful, but many problems also require the actual path. Floyd-Warshall supports this with a next matrix (sometimes called the predecessor or parent matrix).

Alongside the distance matrix, maintain a matrix next[i][j] that stores the next vertex to visit on the shortest path from i to j. When dist[i][j] is updated because going through k is shorter, also update next[i][j] = next[i][k], meaning "to go from i to j, first take the same step as going from i to k."

Using the graph from our earlier walkthrough, calling getPath(1, 0) would return [1, 3, 0], which corresponds to the shortest path of cost 5.

Its O(V^3) time complexity makes it impractical for large graphs. For small or dense graphs, its simplicity is a strong advantage.

Floyd-Warshall vs. Running Dijkstra V Times

The two common approaches to all-pairs shortest paths compare as follows:

For a dense graph where E is close to V^2, Floyd-Warshall and running Dijkstra V times have similar performance. Floyd-Warshall is simpler to implement and debug. For sparse graphs with many vertices, Dijkstra V times wins.

Good Fits for Floyd-Warshall

When to Avoid It

Time Complexity: O(V^3)

The algorithm has three nested loops, each iterating V times. Every cell in the V x V matrix is examined V times (once for each intermediate vertex k).

For V = 100, that is 10^6 operations, which is instant. For V = 500, that is 1.25 * 10^8, which is borderline. For V = 1000, that is 10^9, which is too slow for most judges.

Space Complexity: O(V^2)

The distance matrix requires V^2 space. If path reconstruction is needed, the next matrix adds another V^2. The space is dominated by these matrices, not the algorithm's logic.

When Is O(V^3) Acceptable?

In most competitive programming settings, V <= 400 is the practical limit for Floyd-Warshall.