Floyd-Warshall

The 10-second versionCopy Anchor Link

Floyd-Warshall computes the shortest path between every pair of nodes in one go, using a tiny dynamic program: let the first k vertices be the only ones you are allowed to use as intermediate stops, and grow k from 0 up to V. Three nested loops, an O(V³) sweep, and the distance matrix is done — and it happily tolerates negative edges (though not negative cycles). The exact same machinery, with the arithmetic swapped out, also answers plain reachability: the transitive closure.

Why this existedCopy Anchor Link

Routing changed shape in the 1950s and 1960s. Telephones, power grids, and (soon) computer networks wanted not just "how far is it from here to there," but "how far is everything from everything" — a whole table of distances, built once and consulted millions of times. Running a single-source algorithm V times was the obvious approach, but it felt wasteful, and it did not handle negative edges gracefully.

Meanwhile a second, more abstract question was proving equally important: reachability, or transitive closure. Given a relation like "A can reach B" or "this task depends on that one," what is the full relation, including all the multi-step chains? That is the same computation wearing boolean clothes, and it is where the algorithm was born.

Three names, in order:

• 1959 — Bernard Roy, a French mathematician, publishes the recurrence for transitive closure in "Transitivité et connexité."
• 1962 — Stephen Warshall publishes the graph-reachability version — the boolean kernel.
• 1962 — Robert Floyd adapts the identical loop shape to weighted shortest paths, swapping OR/AND for min/+.

Why it mattered: it was the first algorithm that produced the entire all-pairs table in a single, dead-simple pass — no priority queue, no per-source wrapping, just three loops and an array. And its connection to dynamic programming (pointed out by Dantzig) made it a poster child for the whole paradigm.

Inside the inventor's headCopy Anchor Link

The obvious plan is "run Dijkstra from every node." That works, but it costs O(V · E log V) — and for a dense graph, where E ≈ V², that is O(V³ log V), more expensive than the thing everyone wanted, and it still chokes on negative edges. Bellman-Ford per source is worse. Nobody was happy.

The pivot is a change of question. Instead of "from this source, how far to everywhere?", ask: which vertices am I allowed to route through? Start by allowing none — so the only paths are the direct edges. Then allow vertex 0 as a waypoint. Then allow vertices 0 and 1. Build the table up, one allowed-vertex at a time, and each layer can only ever make distances smaller.

The magic is that each layer only needs the previous layer, so you can keep a single matrix and update it in place. That is what makes it three loops and not four — and the reason the in-place version is still correct is genuinely subtle, so hold that thought; we will unpack it below.

The final approachCopy Anchor Link

The recurrenceCopy Anchor Link

Let D[k][i][j] be the shortest distance from i to j using only the vertices {0, 1, …, k-1} as intermediate stops. Either the best path does not touch vertex k-1, or it does — and then we can split it there:

D[k][i][j] = min( D[k-1][i][j], D[k-1][i][k-1] + D[k-1][k-1][j] )

Drop the extra k dimension (the update is safe in place) and you get the famous triple loop:

for k in 0 .. V-1:
  for i in 0 .. V-1:
    for j in 0 .. V-1:
      if D[i][k] + D[k][j] < D[i][j]:
        D[i][j] = D[i][k] + D[k][j]

Why is in-place safe, when the formula seems to want the previous layer for D[i][k]? Because D[i][k] never improves during layer k. A path from i to k that used k as an interior waypoint would have to pass through k on the way to k — a pointless cycle that cannot lower a non-negative-except-cycles cost. So reading D[i][k] "too early" reads the same value anyway.

The DP layersCopy Anchor Link

The invariantsCopy Anchor Link

• Layer k. After processing layer k, D[i][j] equals the true shortest distance using intermediate vertices drawn only from the first k vertices.
• Monotone shrinking. Every update only lowers an entry, so an entry never has to be "un-improved."
• Diagonal test. After all layers, if any D[i][i] < 0, vertex i sits on a negative cycle — because a shortest "path" from i to itself should be 0, and anything below that is free profit looping forever.

A worked traceCopy Anchor Link

Three nodes A, B, C, with edges A→B = 4, A→C = 5, C→B = -3. The starting matrix (infinity means "no direct edge"):

When k reaches C, the update fires: D[A][B] becomes min(4, D[A][C] + D[C][B]) = min(4, 5 + (-3)) = 2. The negative edge rode in through C, and the layer structure caught it. Final matrix:

It in codeCopy Anchor Link

function floydWarshall(d) {  const n = d.length;  for (let k = 0; k < n; k++)    for (let i = 0; i < n; i++)      for (let j = 0; j < n; j++)        if (d[i][k] + d[k][j] < d[i][j])          d[i][j] = d[i][k] + d[k][j];}

ComplexityCopy Anchor Link

There is no best case to speak of — the loop count never depends on the data, which is part of its charm. Compare it to the alternatives for all pairs: Dijkstra once per source is O(V · E log V) (better on sparse graphs), and Bellman-Ford once per source is O(V² · E). Floyd-Warshall wins on small, dense graphs and whenever negative edges are in play, because its constant is tiny and the code is three lines.

Where you meet it todayCopy Anchor Link

• Small dense all-pairs tables. Routing tables on a modest network, or a precomputed distance matrix for a game map with a few hundred nodes, built once and queried forever.
• Reachability and transitive closure. "Is this module reachable from that one?" "Does this task transitively depend on that one?" is a boolean Floyd-Warshall over the dependency graph.
• Relational databases and DAG tooling. SQL recursive CTEs and tools like dbt compute transitive closure of dependencies — the same recurrence, expressed as a query.
• Graph analytics. Betweenness centrality is built on all-pairs shortest paths (via Brandes' algorithm); Floyd-Warshall is the honest baseline that explains the idea.
• Arbitrage, again. A negative value on the diagonal after the sweep is a negative cycle, and therefore risk-free money.

The boolean sibling is worth seeing side by side — swap min/+ for OR/AND, drop the weights, and you have transitive closure:

// reachability: swap min/+ for OR/AND and drop the weightsfor (let k = 0; k < n; k++)  for (let i = 0; i < n; i++)    if (reach[i][k])      for (let j = 0; j < n; j++)        if (reach[k][j]) reach[i][j] = true;

RecapCopy Anchor Link

• Floyd-Warshall gives all-pairs shortest paths with a single O(V³) triple loop over an O(V²) matrix.
• The dynamic program grows the set of allowed intermediate vertices one k at a time; each layer only shrinks distances.
• It tolerates negative edges but not negative cycles — a negative value on the diagonal (D[i][i] < 0) flags one.
• Replace min/+ with OR/AND and it computes transitive closure (plain reachability).
• It shines on small, dense graphs or whenever you want every pair at once.

Next up: A* Search — take Dijkstra and point it at a single target, with a hunch about which way to go.