Floyd-Warshall, Johnson Reweighting, and the All-Pairs Choice

All-pairs shortest paths asks for the distance between every ordered pair of vertices: a matrix of $|V|^2$ entries. Both classical methods produce that matrix, and they are usually presented as alternatives on the basis of density. The more consequential difference is what they do about negative edge weights, because one absorbs them into the recurrence and the other removes them by changing the weights.

The triple loop and what its index order means

Floyd-Warshall computes $D^{(k)}[i][j]$, the length of the shortest path from $i$ to $j$ whose interior vertices are drawn from ${1, \dots, k}$. The recurrence is

$$D^{(k)}[i][j] = \min\big( D^{(k-1)}[i][j],; D^{(k-1)}[i][k] + D^{(k-1)}[k][j] \big),$$

with $D^{(0)}$ the adjacency matrix, zero on the diagonal and $\infty$ where no edge exists.

The correctness argument is a case split on vertex $k$. Either the shortest path avoids $k$ entirely, in which case it is already in $D^{(k-1)}$, or it visits $k$; and if it visits $k$, the prefix and suffix are shortest paths with interiors in ${1,\dots,k-1}$, because any repetition of a vertex in a shortest path would allow a cycle to be removed. This is the optimal-substructure argument from Relaxation and the Optimality Condition applied to a state space indexed by the permitted interior set.

INF = float('inf')

def floyd_warshall(n, w):
    """w is an n x n matrix; w[i][j] = INF when there is no edge."""
    d = [row[:] for row in w]
    for i in range(n):
        d[i][i] = 0
    for k in range(n):
        dk = d[k]                      # hoist the row: the inner loop reads it n times
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue               # no route through k from i; skip the whole row
            di = d[i]
            for j in range(n):
                alt = dik + dk[j]
                if alt < di[j]:
                    di[j] = alt
    return d

The update is in place, and that is safe because $D^{(k)}[i][k] = D^{(k-1)}[i][k]$: any path from $i$ to $k$ with interior vertices in ${1,\dots,k}$ that visits $k$ internally would contain a cycle through $k$, which cannot be shorter than the path without it when weights are nonnegative on that cycle. With negative weights the identity still holds for the distances themselves, because a shortest path never revisits a vertex, so the in-place update is correct for arbitrary weights as long as no negative cycle exists.

The loop order is not interchangeable. Swapping the $k$ loop inward computes something else entirely: it becomes a relaxation scheme with a different and weaker invariant, and on graphs with negative weights it can produce values below the true distance. The three-level nesting must have the intermediate-vertex loop outermost.

Cost is $\Theta(|V|^3)$ time and $\Theta(|V|^2)$ space for the distance matrix, with a further $\Theta(|V|^2)$ if a next-hop matrix is carried for path reconstruction. For $|V| = 1000$ the triple loop is on the order of $10^9$ inner iterations, a count a single thread can work through with a tight min-plus update over contiguous rows. For $|V| = 10^5$ it is $10^{15}$, which is not a number of iterations any machine will complete. The method’s usable range is bounded by the cube, and that bound is the reason sparse graphs use the other approach.

Negative cycles inside the triple loop

A negative cycle shows up on the diagonal: after the algorithm finishes, $D[i][i] < 0$ for every vertex $i$ that can reach and be reached from a negative cycle. The value is not meaningful as a distance, since it is the best closed walk and the true shortest path from $i$ to $i$ is the empty path of length zero, but the sign is a reliable detector, and it costs one pass over $|V|$ entries.

Partial detection is also available. If the diagonal is checked after each $k$ iteration, the first $k$ at which a diagonal entry turns negative identifies the smallest-index vertex set whose inclusion creates the cycle. That is occasionally useful when the cycle has to be reported rather than merely flagged, and it is the all-pairs analogue of the extra-pass trick in Bellman-Ford, Round Counts, and Negative-Cycle Detection.

Johnson’s reweighting

Johnson’s method takes the opposite route: make the weights nonnegative, then run a one-to-all algorithm from each vertex. If a potential $\pi(v)$ is assigned to each vertex and each edge weight is replaced by

$$c’(u,v) = c(u,v) + \pi(u) - \pi(v),$$

then for any path $p$ from $s$ to $t$,

$$c’(p) = c(p) + \pi(s) - \pi(t),$$

because the potentials telescope along the path. Every path between a fixed pair shifts by the same amount, so the shortest path is unchanged, and its length can be recovered by subtracting $\pi(s) - \pi(t)$ from the computed value.

The reduced costs are nonnegative for every edge exactly when $\pi(v) \le \pi(u) + c(u,v)$, that is, when $\pi$ satisfies the fixed-point inequality of a shortest-path problem rooted at an imaginary source. So the potentials are themselves a shortest-path solution, which suggests how to obtain them: add a new vertex $q$ with a zero-weight edge to every vertex, run Bellman-Ford from $q$, and set $\pi(v) = d[q][v]$. The distances from $q$ satisfy the inequality by construction, and a negative cycle reachable from $q$, which is any negative cycle at all, makes the Bellman-Ford run report it.

def johnson(n, edges, dijkstra):
    """edges: (u, v, w) triples. dijkstra(n, adj, s) -> list of distances."""
    extra = edges + [(n, v, 0) for v in range(n)]
    # bellman_ford(n, edges, source) -> (dist, parent, has_negative_cycle)
    h, _, has_cycle = bellman_ford(n + 1, extra, n)
    if has_cycle:
        raise ValueError("negative cycle")
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w + h[u] - h[v]))            # nonnegative by construction
    out = []
    for s in range(n):
        d = dijkstra(n, adj, s)
        out.append([x + h[v] - h[s] if x < float('inf') else x for v, x in enumerate(d)])
    return out

The cost is one Bellman-Ford run at $O(|V||E|)$ plus $|V|$ Dijkstra runs. With a binary heap the total is $O(|V| \cdot |E| \log |V|)$ on a sparse graph, which is $O(|V|^2 \log |V|)$ when $|E|$ is proportional to $|V|$, better than the cube for sparse graphs and worse for dense ones, where $|V||E|$ reaches $|V|^3 \log |V|$ and the triple loop wins.

The comparison that matters

The two methods differ on four axes.

Density: Floyd-Warshall’s cost is independent of $|E|$, so it is optimal when the graph is dense enough that $|E|$ approaches $|V|^2$. Johnson’s cost grows with $|E|$, so it is optimal when $|E|$ is small. The crossover is where $|E| \log |V|$ overtakes $|V|^2$, roughly $|E| \approx |V|^2 / \log |V|$.

Memory: Floyd-Warshall needs a full $|V|^2$ matrix, which for a million vertices is $10^{12}$ entries and out of reach. Johnson needs the graph plus one distance vector at a time, so it can stream results to disk; only the output matrix is $|V|^2$.

Negative edges: both handle them. Floyd-Warshall does so directly; Johnson does so by removing them. The difference is that Johnson’s Bellman-Ford step reports a negative cycle explicitly, while Floyd-Warshall’s detection is a diagonal scan and gives less information about which cycle it is.

Early termination and partial queries: Floyd-Warshall computes everything whether or not it is needed. Johnson computes one row per source, so a caller that needs a handful of rows pays for only those.

There is a third option worth naming: repeated Dijkstra without reweighting. On nonnegative graphs it is exactly Johnson without the Bellman-Ford step, and it is what most libraries do. The reweighting step exists solely to extend that to negative weights.

Where the cubic loop still earns its place

Two situations keep Floyd-Warshall in use. The first is transitive-closure-style queries on small dense graphs, such as reachability in a dependency graph of a few hundred nodes, where the constant factor of a tight min-plus loop over contiguous rows is small and the alternative’s pointer chasing is not. The second is as a subroutine: the minimum-mean-cycle computation in Minimum Mean Cycle and the Shape of Negative-Weight Answers needs distances between all pairs of a small graph, and the dynamic program over path length that underlies it is a variant of the same recurrence.

For the large sparse case, neither method is the right answer on road networks. The preprocessing methods in Contraction Hierarchies and Preprocessing for Road Networks replace the per-query all-pairs cost with an offline build and a query that is orders of magnitude cheaper than a Dijkstra run, and they are the reason all-pairs tables are no longer the standard answer for geographic routing.

One further caution applies to both methods. The distance matrix of a graph with zero-weight edges can contain ties that make the reconstructed path ambiguous, and implementations that store a single next-hop per pair will report one of several equal-cost paths without indicating the choice. Where the distinction matters, for instance when the path must avoid a particular edge, the next-hop matrix is insufficient and the path has to be recomputed under the added constraint.