Floyd-Warshall Algorithm

A Bit of History

Few algorithms have as tangled a discovery history. French mathematician Bernard Roy published essentially the same triple-loop technique in 1959 for computing transitive closure. Three years later, in 1962, Stephen Warshall independently published a clean Boolean version for the same transitive-closure problem, and in the very same year, Robert Floyd independently adapted the identical loop structure to compute shortest-path distances rather than mere reachability. Floyd's short paper, titled simply "Algorithm 97: Shortest Path," is barely a page long — one of the most compact and consequential algorithm descriptions ever published. Because of this tangled parallel discovery, you'll see the algorithm called "Floyd-Warshall," "Roy-Warshall," or occasionally "Roy-Floyd-Warshall" depending on the textbook.

Working Principle

Floyd-Warshall computes all \(V^2\) shortest distances via dynamic programming over allowed intermediate vertices. Define \(d_k[i][j]\) as the shortest distance from \(i\) to \(j\) using only vertices \(\{1, \dots, k\}\) as intermediate stops. The recurrence considers exactly one question per step: does routing through vertex \(k\) help?

$$d_k[i][j] = \min\big(d_{k-1}[i][j],\ d_{k-1}[i][k] + d_{k-1}[k][j]\big)$$

Remarkably, the entire 3-dimensional DP can be computed in place using a single 2D matrix, since each update only ever reads values that are still valid for the current \(k\):

def floyd_warshall_pseudocode(dist):
    """dist: V x V matrix, dist[i][j] = edge weight or infinity if no edge, 0 on diagonal."""
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]   # route i -> k -> j is shorter
    return dist

Worked Example

A 3-vertex graph: \(A \to B\) (3), \(B \to C\) (1), \(A \to C\) (10).

flowchart LR
    A -->|3| B
    B -->|1| C
    A -.->|"10 (direct)"| C
            

Before considering \(B\) as an intermediate, \(d[A][C] = 10\) (the only known route). When \(k = B\), the algorithm checks: is \(d[A][B] + d[B][C] = 3 + 1 = 4\) less than \(d[A][C] = 10\)? Yes — update \(d[A][C]\) to 4. This single check, repeated for every \((i,j)\) pair and every intermediate \(k\), is the entire algorithm.

Why the DP Recurrence Works

This is induction on \(k\), in the style of Part 1. Claim: after processing intermediate vertex \(k\), \(d[i][j]\) equals the true shortest distance from \(i\) to \(j\) using only \(\{1,\ldots,k\}\) as intermediates. Base case (\(k=0\), no intermediates allowed): \(d[i][j]\) is just the direct edge weight (or \(\infty\)), correctly initialized. Inductive step: the true shortest path using vertices up to \(k\) either avoids \(k\) entirely (so the Part \(k-1\) value is already correct and unchanged) or passes through \(k\) exactly once (since revisiting \(k\) would only add cost, assuming no negative cycles) — splitting it into a best path to \(k\) and a best path from \(k\), both using only \(\{1,\ldots,k-1\}\) as intermediates, both already correct by the inductive hypothesis. The recurrence takes the minimum of these two cases, which is exactly correct.

Detecting Negative Cycles

After running the algorithm, check the diagonal: if any \(d[i][i] < 0\), a negative cycle passes through \(i\) — a vertex "improving its distance to itself" can only mean a cycle with negative total weight exists. This mirrors Bellman-Ford's extra-round check, adapted to the all-pairs setting.

Complexity Analysis

Three nested loops over all \(V\) vertices:

$$\text{Time: } O(V^3) \qquad \text{Space: } O(V^2)$$

No dependency on \(E\) at all — Floyd-Warshall's cost is identical whether the graph is sparse or dense, which is exactly why it's the wrong choice for large sparse graphs (Johnson's algorithm, Part 10, wins there) but an excellent, simple choice for dense or small graphs where \(V\) is modest.

Implementation

def floyd_warshall(vertices, edges):
    """
    edges: list of (u, v, weight).
    Returns (dist, has_negative_cycle) where dist is a dict-of-dicts.
    """
    INF = float('inf')
    dist = {i: {j: (0 if i == j else INF) for j in vertices} for i in vertices}
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # keep the cheapest parallel edge

    for k in vertices:
        for i in vertices:
            if dist[i][k] == INF:
                continue
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    has_negative_cycle = any(dist[v][v] < 0 for v in vertices)
    return dist, has_negative_cycle

vertices = ["A", "B", "C"]
edges = [("A", "B", 3), ("B", "C", 1), ("A", "C", 10)]

dist, has_neg = floyd_warshall(vertices, edges)
print(dist["A"]["C"])   # 4 (via B), not 10
print(has_neg)           # False

#include <vector>
#include <limits>
#include <iostream>
using namespace std;

int main() {
    const long long INF = numeric_limits<long long>::max() / 2;
    int n = 3; // A=0, B=1, C=2
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;

    dist[0][1] = 3;  // A -> B
    dist[1][2] = 1;  // B -> C
    dist[0][2] = 10; // A -> C (direct)

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    bool hasNegativeCycle = false;
    for (int i = 0; i < n; i++) if (dist[i][i] < 0) hasNegativeCycle = true;

    cout << "Distance A->C: " << dist[0][2] << endl; // 4
    return 0;
}

import java.util.*;

class FloydWarshall {
    public static void main(String[] args) {
        long INF = Long.MAX_VALUE / 2;
        int n = 3; // A=0, B=1, C=2
        long[][] dist = new long[n][n];
        for (long[] row : dist) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) dist[i][i] = 0;

        dist[0][1] = 3;  // A -> B
        dist[1][2] = 1;  // B -> C
        dist[0][2] = 10; // A -> C (direct)

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];

        boolean hasNegativeCycle = false;
        for (int i = 0; i < n; i++) if (dist[i][i] < 0) hasNegativeCycle = true;

        System.out.println("Distance A->C: " + dist[0][2]);  // 4
    }
}

Real-World Applications

Exercises

1. Run Floyd-Warshall by hand on a 4-vertex graph of your choosing, tracking the distance matrix after each value of \(k\).
2. Modify the Python implementation to also reconstruct the actual shortest path (not just its length) using a "next hop" matrix updated alongside `dist`.
3. Explain why Floyd-Warshall's in-place update (a single matrix, not three separate \(d_{k-1}\), \(d_k\) copies) is still correct, even though it appears to mix values from different \(k\) at first glance.
4. Challenge: Implement Warshall's Boolean transitive-closure variant (replace min/plus with OR/AND) and verify it correctly computes reachability on a directed graph with a cycle.

Limitations