Floyd-Warshall all-pairs shortest paths

What this chapter covers

Dijkstra and Bellman-Ford both answer "shortest paths from one source." Sometimes you need all of them — the shortest distance between every pair of nodes: a full distance table for a road network, the transitive reachability of a dependency graph, the tightest bound between every pair of variables in a constraint system. Floyd-Warshall computes that entire V×V matrix in one of the shortest, strangest, most elegant pieces of code in this book — a triple-nested loop whose body is a single line. It handles negative edges like Bellman-Ford, detects negative cycles by looking at its own diagonal, and its dense, regular memory access makes it run close to hardware speed despite its $O(V^3)$ cost. This chapter builds it, watches the distance matrix fill in one intermediate node at a time, and measures where its blunt all-at-once approach beats the alternative of running Dijkstra from every node.

A bit of history

The algorithm is named for Robert Floyd, who published it in 1962, and Stephen Warshall, who published essentially the same idea the same year for computing the transitive closure of a relation — whether each node can reach each other, the boolean version of the shortest-path problem. Bernard Roy had described it as early as 1959, so it's occasionally called the Roy-Floyd-Warshall algorithm. Warshall's contribution was the crucial insight that survives in the loop structure: to know whether $i$ can reach $j$, consider intermediate nodes one at a time, and allowing one more possible waypoint can only add reachability. Floyd carried the same idea to weighted shortest paths by replacing "or" with "min" and "and" with "plus." That correspondence — reachability is shortest paths over the boolean semiring, shortest paths is reachability over the min-plus semiring — is why the same three lines solve both, and it's a small, beautiful example of how one algorithm skeleton generalizes across problems by swapping the arithmetic.

The intuition

Here's the dynamic-programming idea, and it's subtle enough to be worth stating carefully. Number the nodes 0 to V−1. Define the subproblem: what is the shortest distance from $i$ to $j$ if the path is only allowed to pass through intermediate nodes drawn from $\{0, 1, \dots, k-1\}$? Call it $D_k[i][j]$. When $k = 0$, no intermediates are allowed at all, so $D_0[i][j]$ is just the direct edge (or infinity). Now grow $k$ by one — permit node $k$ as a waypoint too. For each pair $(i, j)$, either the best path still doesn't use $k$ (the old value stands), or it does, in which case it goes $i \rightsquigarrow k \rightsquigarrow j$ using only earlier intermediates on each half, which is $D_k[i][k] + D_k[k][j]$. So the update is $$D_{k+1}[i][j] = \min(D_k[i][j],\ D_k[i][k]

• D_k[k][j])$$. After you've allowed every node as an intermediate, the restriction is gone and you have the true shortest distances.

The astonishing part is that you don't need to keep a separate matrix per $k$ — you can update the single matrix in place, provided the loop over $k$ is the outermost one. That ordering guarantees that when you read $dist[i][k]$ and $dist[k][j]$, they already reflect all intermediates below $k$, which is exactly what the recurrence needs. Get the loop order wrong — put $k$ inside — and the algorithm silently computes garbage. The whole thing is three lines, and every subtlety lives in the fact that $k$ comes first.

Complexity: how it scales

Three nested loops over V nodes give $O(V^3)$ time and $O(V^2)$ space for the matrix. That's fixed regardless of how many edges the graph has — Floyd-Warshall touches every cell of the matrix for every intermediate node whether the graph is nearly empty or complete. The alternative for all-pairs is to run a single-source algorithm from each of the V nodes: Dijkstra from every source is $O(V \cdot (V+E)\log V)$, which is cheaper on sparse graphs but grows with edge count. So which wins depends on density, and that's the face-off — the same all-pairs answer, computed both ways, as the graph gets denser:

Notice the shapes, not just the heights. Floyd-Warshall's line is essentially flat — its cost doesn't care how many edges exist, because it always processes the whole matrix. Dijkstra-from-every-node climbs steadily as edges pile up, because each Dijkstra run does more work on a denser graph. On a sparse graph (average out-degree 2) running Dijkstra V times was about five times faster; by out-degree 80 that advantage had shrunk to 1.4×, and the lines are converging. In a compiled language the crossover actually arrives — Floyd-Warshall's tight, branch-free, cache-friendly inner loop overtakes the pointer-chasing heap operations of Dijkstra on dense graphs. Here in pure Python the interpreter's per-operation overhead keeps the simple triple loop behind, but the trend is the real lesson: Floyd-Warshall's price is blind to density, so the denser the graph, the more its brute simplicity pays off.

What it's good at, what it isn't

Floyd-Warshall shines when you genuinely need all-pairs distances and the graph is small or dense: a few hundred nodes, or a graph where edges are abundant. Its three-line body is trivial to implement correctly (once you get the loop order right), it handles negative edges that would need Bellman-Ford per source otherwise, and its regular array access is cache-friendly and vectorizes well, which is why scipy and networkx implement it in compiled code. It's also the natural tool for transitive closure, for "tightening" a matrix of constraints to its implied bounds, and for any min-plus / semiring computation over all pairs.

Where it's the wrong choice is large sparse graphs. Its $O(V^3)$ time and, worse, $O(V^2)$ memory are fixed costs: a million-node road network would need a trillion-entry matrix, which is absurd, while Dijkstra from a single source runs in near-linear time and touches only reachable nodes. For single-source queries it's pure waste — you'd compute the whole matrix to read one row. And on sparse all-pairs problems, running Dijkstra (or Bellman-Ford, for negatives, via Johnson's algorithm) from each node is asymptotically better. Floyd-Warshall is a small-dense-graph specialist, not a general shortest-path tool.

The data, or the inputs

The face-off runs on 140-node random directed graphs of increasing density and times the full all-pairs computation two ways: Floyd-Warshall's triple loop versus running Dijkstra from every node. Correctness is cross-checked three independent ways — against Dijkstra-from-every-node on non-negative graphs, against Bellman-Ford-from-every-node on graphs with negative edges, and by confirming every reconstructed path's edges sum to its matrix distance — plus planted negative cycles to confirm diagonal detection. The animation runs on a small six-node graph and shows the distance matrix itself: each cell is a distance (∞ where there's no path yet), and you watch cells improve as each new intermediate node is switched on.

Build it, one function at a time

The whole algorithm — initialize with direct edges, then the triple loop:

def floyd_warshall(n, edges):
    """All-pairs shortest distances. `edges` is a list of (u, v, w), any sign. Build the
    matrix of direct edges, then for each intermediate node k, ask of every pair (i, j)
    whether going i → k → j beats the best i → j found so far. After all k, the matrix holds
    every shortest distance. O(V^3) time, O(V^2) space. The order of the loops matters: k
    MUST be outermost, so that when we use dist[i][k] and dist[k][j] they already account for
    intermediates < k."""
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w                   # keep the cheapest parallel edge
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                     # i can't reach k, so k is no help from i
            di = dist[i]
            for j in range(n):
                through_k = dik + dk[j]
                if through_k < di[j]:
                    di[j] = through_k        # routing i → k → j is cheaper
    return dist

The same loop keeping a next-hop matrix, so any shortest path can be rebuilt:

def floyd_warshall_paths(n, edges):
    """Same algorithm, but remember a next-hop matrix so any shortest path can be rebuilt.
    nxt[i][j] is the first node to step to when going from i toward j."""
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        nxt[i][i] = i
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]     # first step toward k is the first step toward j
    return dist, nxt


def reconstruct(nxt, i, j):
    """Walk the next-hop matrix to list the actual shortest path i → j (or None if none)."""
    if nxt[i][j] is None:
        return None
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path

And negative-cycle detection, straight off the diagonal:

def has_negative_cycle(dist):
    """After Floyd-Warshall, a node reachable more cheaply than 0 *from itself* sits on a
    negative cycle — going around the loop lowered its own distance below zero."""
    return any(dist[i][i] < 0 for i in range(len(dist)))

Watch it work

Here's the distance matrix for a six-node graph as Floyd-Warshall runs. Each cell $(i, j)$ holds the current best distance from $i$ to $j$; the teal diagonal is the zero distance from a node to itself, and dark cells are ∞ — no path known yet. The first frame is direct edges only. Then, one frame at a time, we switch on each node as a permitted intermediate: cells that improve flash orange. Watch how allowing node 1 as a waypoint fills in $0 \to 2$ (via $0 \to 1 \to 2$), and how later intermediates ripple longer routes into place. By the last frame the matrix holds every shortest distance — the entire all-pairs answer, assembled one waypoint at a time:

The complete code

The from-scratch tab is Floyd-Warshall with path reconstruction and cycle detection; the library tab is the Dijkstra-from-every-node strategy it's raced against (and checked against), with the networkx and scipy calls you'd actually use noted at the top. Flip between them.

"""Floyd-Warshall — the shortest distance between EVERY pair of nodes, all at once, in a
strikingly short triple loop. Where Dijkstra and Bellman-Ford answer "shortest paths from
one source," Floyd-Warshall fills the whole V×V distance matrix. It handles negative edges
like Bellman-Ford, detects negative cycles (a node ends up cheaper than zero from itself),
and its inner loop is so simple and regular it runs close to hardware speed.

The idea is dynamic programming over an unusual dimension: not "paths of at most k edges"
(that was Bellman-Ford) but "paths allowed to route through only the first k nodes as
intermediates." Start with direct edges only (no intermediates). Then permit node 0 as a
waypoint and relax; then also node 1; and so on. After every node has been allowed as an
intermediate, dist[i][j] is the true shortest distance. That's the entire algorithm:

    for k: for i: for j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
"""

INF = float("inf")


# region: floyd_warshall
def floyd_warshall(n, edges):
    """All-pairs shortest distances. `edges` is a list of (u, v, w), any sign. Build the
    matrix of direct edges, then for each intermediate node k, ask of every pair (i, j)
    whether going i → k → j beats the best i → j found so far. After all k, the matrix holds
    every shortest distance. O(V^3) time, O(V^2) space. The order of the loops matters: k
    MUST be outermost, so that when we use dist[i][k] and dist[k][j] they already account for
    intermediates < k."""
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w                   # keep the cheapest parallel edge
    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                     # i can't reach k, so k is no help from i
            di = dist[i]
            for j in range(n):
                through_k = dik + dk[j]
                if through_k < di[j]:
                    di[j] = through_k        # routing i → k → j is cheaper
    return dist
# endregion


# region: with_paths
def floyd_warshall_paths(n, edges):
    """Same algorithm, but remember a next-hop matrix so any shortest path can be rebuilt.
    nxt[i][j] is the first node to step to when going from i toward j."""
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        nxt[i][i] = i
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]     # first step toward k is the first step toward j
    return dist, nxt


def reconstruct(nxt, i, j):
    """Walk the next-hop matrix to list the actual shortest path i → j (or None if none)."""
    if nxt[i][j] is None:
        return None
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path
# endregion


# region: negative_cycle
def has_negative_cycle(dist):
    """After Floyd-Warshall, a node reachable more cheaply than 0 *from itself* sits on a
    negative cycle — going around the loop lowered its own distance below zero."""
    return any(dist[i][i] < 0 for i in range(len(dist)))
# endregion

"""The library counterpart and the contrast. In production, all-pairs shortest paths come
from networkx (`nx.floyd_warshall_numpy`) or scipy (`scipy.sparse.csgraph.shortest_path`),
both of which drop into compiled/vectorized code for the O(V^3) work:

    import networkx as nx
    D = nx.floyd_warshall_numpy(G, weight="weight")   # a V×V distance matrix

The instructive comparison, though, is against the ALTERNATIVE strategy for all-pairs on
non-negative graphs: run Dijkstra from every source. That's O(V·(V+E) log V), which beats
Floyd-Warshall's O(V^3) on sparse graphs but loses on dense ones — the trade the face-off
measures. `all_pairs_dijkstra` below is that strategy, and also the trusted reference the
trace generator checks Floyd-Warshall against on non-negative graphs.
"""
import heapq

INF = float("inf")


# region: all_pairs_dijkstra
def dijkstra(adj, start, n):
    dist = [INF] * n
    dist[start] = 0
    settled = [False] * n
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if settled[u]:
            continue
        settled[u] = True
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist


def all_pairs_dijkstra(n, edges):
    """Run Dijkstra from every node → the full distance matrix, in O(V·(V+E) log V). Correct
    only for non-negative weights (Dijkstra's requirement), and the strategy Floyd-Warshall
    competes with on such graphs."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    return [dijkstra(adj, s, n) for s in range(n)]
# endregion

Scratch vs library

The comparison here isn't correctness — Floyd-Warshall and Dijkstra-from-every-node agree exactly on non-negative graphs, as the checks confirm. It's a decision about strategy for the same all-pairs goal, and it turns on the graph's shape. Floyd-Warshall does a fixed $O(V^3)$ of dense, regular work regardless of edges; Dijkstra-per-node does less work when edges are scarce and more when they're plentiful. So the honest answer to "which all-pairs algorithm" is "it depends on density and size," and the chart shows exactly the trade: a flat line against a rising one. This is a recurring shape in this book — asymptotically identical goals with different constant factors and different sensitivities, where the right pick depends on the regime you're in. In production you'd reach for scipy's or networkx's compiled Floyd-Warshall on small dense graphs and Dijkstra-per-node (or Johnson's, for negatives) on large sparse ones; building the triple loop once is what makes the loop-order subtlety and the density trade-off concrete instead of memorized.

Where you'll actually meet it

Floyd-Warshall runs wherever a small, dense all-pairs answer is needed. Network analysis tools compute it to get every-pair latencies and to derive metrics like a graph's diameter and betweenness centrality. It's the classic method for the transitive closure of a relation — reachability in dependency graphs, type-subtyping lattices, database query optimization. Compilers and static analyzers use its min-plus form to tighten systems of difference constraints and to compute inter-procedural summaries. It appears in regular-expression-to-automaton constructions (Kleene's algorithm is the same loop over a different semiring), in routing-table precomputation for small networks, and across operations research anywhere an all-pairs cost matrix is wanted. Whenever the graph is small enough that a $V^2$ matrix fits and you want every distance, Floyd-Warshall's three lines are the tool.

Takeaways

Floyd-Warshall computes all-pairs shortest distances by dynamic programming over which nodes are allowed as intermediates — grow the allowed set one node at a time, updating in place with $k$ outermost — in $O(V^3)$ time and $O(V^2)$ space. It handles negative edges and detects negative cycles off its own diagonal, and the same three-line skeleton computes transitive closure by swapping min/plus for or/and. Its cost is independent of edge count, so it's the specialist for small or dense all-pairs problems, and the wrong tool for large sparse graphs, where per-node Dijkstra wins on both time and memory.

With Floyd-Warshall the shortest-path thread of this tier closes: unweighted (BFS), non-negative single-source (Dijkstra), negative single-source (Bellman-Ford), all-pairs (Floyd-Warshall). The next chapter, A*, returns to single-source but adds a new idea — a heuristic that estimates the remaining distance to a specific goal, steering the search so it explores far fewer nodes than Dijkstra when you know where you're headed.