Dijkstra answers "how far is everything from here?". Floyd-Warshall answers "how far is everything from everything?", and does it with the shortest serious algorithm in this family: three nested loops and one comparison. The idea inside is dynamic programming over stopovers: after considering node k, every distance is optimal among paths that only route through the first k nodes. Run k across all V nodes and every pair's true shortest distance sits in an V × V matrix.

The price is O(V³) regardless of how few edges exist, and the payoff is generality: all pairs at once, negative edges handled, and a free negative-cycle detector built into the diagonal.

The recurrence reads like a travel question. The best route from i to j using stopovers from the first k nodes either ignores node k entirely, or goes i → k → j with each half using only earlier stopovers: min(dist[i][j], dist[i][k] + dist[k][j]). Watch one update land on a 4-node graph with edges 1→3 at -2, 3→4 at 2, 4→2 at -1, 2→1 at 4, and 2→3 at 3. There is no direct edge from 1 to 4, so that cell starts at infinity. Predict its value once node 3 is allowed as a stopover.

It becomes 0: the splice 1→3 plus 3→4 costs -2 + 2. One round later, with node 4 admitted, the cell for 1→2 drops to -1 by extending that same route with the 4→2 edge, and the final matrix holds every pair's optimum, negative edges and all. Each round is cheap. The power is that V rounds compound.

INF = float("inf")

def floyd_warshall(dist: list[list[float]]) -> list[list[float]]:
    # dist starts as the adjacency matrix: 0 on the diagonal,
    # edge weights where edges exist, INF everywhere else
    n = len(dist)

    # k MUST stay the outermost loop
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # Either keep the path, or route it through k
                through_k = dist[i][k] + dist[k][j]
                if through_k < dist[i][j]:
                    dist[i][j] = through_k

    return dist

You might think three symmetric loops can be nested in any order, and this is the one algorithm where that instinct writes a bug that compiles, runs, and returns plausible garbage. The correctness argument needs every value read during round k, the dist[i][k] and dist[k][j] halves, to be finished products of round k - 1. With k outermost that holds automatically, because round k never modifies row k or column k: routing from i to k through k adds nothing.

Bury k inside and each cell mixes stopover sets from different rounds, so some pairs miss routes entirely. The result is the worst kind of wrong: close enough to pass small tests. Memorize one fact about this algorithm and make it the loop order.

Unlike Dijkstra, Floyd-Warshall never finalizes anything early, so negative edges are business as usual: the splice comparison simply finds the cheaper route, whatever its sign. What no shortest path algorithm survives is a negative cycle, a loop whose total weight is below zero, because walking it again always improves the trip and "shortest" stops meaning anything.

Floyd-Warshall detects that for free. Every diagonal entry dist[i][i] starts at 0, and the only way it can end below zero is a round trip from i back to itself with negative total cost. Scan the diagonal after the loops: any negative entry names a node on a negative cycle, and distances through that region should be treated as undefined rather than reported.

Reach for it when the node count is small (a few hundred), the graph is dense, or many distance queries follow one precomputation. Find the City With the Smallest Number of Neighbors is the signature problem: n ≤ 100 cities and a question about every city's distance to every other city, which is the all-pairs matrix read twice. The transitive-closure variant (replace the arithmetic with booleans) answers batched reachability questions like Course Schedule IV's prerequisite queries in O(1) each.

The contrast worth internalizing: this is not "Dijkstra run V times". That approach is faster on sparse non-negative graphs, while Floyd-Warshall wins on density, on negative edges, and on sheer unforgettability. Three loops, one comparison, no heap.

Almost every Floyd-Warshall bug lives outside the three loops:

Two checks first: what does dist[i][j] mean after round k finishes, and why does a negative value on the diagonal prove a negative cycle? The set is small because the algorithm picks its spots, and each problem below is one of them: