subroute.
Advanced11 min readlive prototype

Floyd-Warshall

All-pairs shortest paths in three nested loops. A dense-matrix DP that's still the right tool when you need every distance.

Overview

What this concept solves

*Floyd-Warshall computes the shortest path between every pair of nodes — in three nested loops.* No priority queues, no relaxation queues, just a V×V distance matrix and a triple for loop. The algorithm is roughly five lines long and still ships in production whenever the graph is small and dense enough that 'all pairs at once' is what you actually want.

The trick is dynamic programming over intermediate nodes. Define dist[k][i][j] as the shortest path from i to j using only nodes {1, 2, …, k} as intermediates. The base case is dist[0][i][j] = the direct edge weight (or ∞). The recurrence is dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j]) — either you skip node k and use the answer you had, or you go through k. After processing every k from 1 to V, the matrix holds shortest paths using any intermediate, i.e. the true all-pairs shortest paths.

The standard implementation drops the k dimension by overwriting the matrix in place — the recurrence is safe to do that because the row and column for k don't change during pass k. The runtime is O(V³), the memory is O(V²), and the algorithm handles negative edges (but not negative cycles — those make the answer undefined, and Floyd-Warshall detects them via a negative diagonal entry).

Mechanics

How it works

The algorithm in three loops

  1. Initialise: dist[i][j] = w(i, j) for every edge, dist[i][i] = 0, everything else ∞.
  2. For every intermediate node k:
  3.   For every source i:
  4.     For every target j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  5. Done. dist[i][j] is the shortest path from i to j for every pair.

Why the order of loops matters

  • `k` must be the outermost loop. It corresponds to adding intermediate nodes one at a time. After pass k, every shortest path that uses only {1, …, k} as intermediates is correctly computed.
  • Swapping i or j to be outer breaks the recurrence: you'd update dist[i][j] using an already-updated dist[i][k] or dist[k][j], double-counting node k.
  • Negative-cycle detection: after the algorithm finishes, check every diagonal entry. If dist[i][i] < 0 for any i, that node sits on a negative cycle, and shortest paths involving it are undefined.
  • Path reconstruction: keep a next[i][j] matrix and update next[i][j] = next[i][k] whenever you take the through-k branch. Walk the matrix to rebuild the path.

Compare with V calls to Dijkstra

V independent Dijkstra runs cost O(V · (V + E) log V). On a sparse graph (E ≈ V) that's O(V² log V), beating Floyd-Warshall's O(V³). On a dense graph (E ≈ V²) it's O(V³ log V), so Floyd-Warshall wins. The crossover is at roughly E ≈ V² / log V — but for V < a few hundred, Floyd-Warshall's tiny constant factor often makes it the practical winner regardless.

Use a sentinel for infinity carefully

dist[i][k] + dist[k][j] overflows if both are INT_MAX. Real implementations use Long.MAX_VALUE / 2 (or Infinity in JS) as the sentinel, or skip the addition when either operand is the sentinel. This bites everyone the first time they write Floyd-Warshall in C/Java.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A V×V distance matrix lit up cell-by-cell. Press Play to watch Floyd-Warshall sweep through every intermediate node k, every source i, and every target j, asking 'is i → k → j cheaper than the direct path I had before?'. Step / Back walk one cell update at a time.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through a full V³ sweep

Press Play and watch the matrix light up one cell at a time. The orange highlight tracks the current (k, i, j) triple. Notice the cells that change: each update is a discovery that going through k is cheaper than the previous best.

try 02

Step through cell by cell

Hit Step to advance one (k, i, j) update. The narration tells you whether the new path i → k → j improved on the existing dist[i][j]. Back rewinds the update: the cell returns to its pre-update value.

try 03

Try a different graph

Switch the Graph dropdown between Dense, Path, and Negative edge. Watch how the matrix fills in differently — dense graphs fill from the start, path graphs fill column-by-column, and negative edges produce mid-algorithm distance drops you wouldn't see in Dijkstra.

try 04

Find the graph's diameter

After the algorithm finishes, scan the matrix for the largest finite entry. That's the graph's diameter — the longest shortest-path distance between any two nodes. The graph's radius (min row-max) tells you the most central node — a useful primitive for facility-location problems.

In practice

When to use it — and what you give up

When it's the right tool

  • All-pairs shortest paths on a small dense graph — anywhere V < ~500 and you want every pair, Floyd-Warshall's three lines beat the V-Dijkstras setup overhead.
  • Transitive closure — replace min(+) with OR(AND) and you get the boolean reachability matrix (Warshall's original 1962 algorithm).
  • Network diameter / radius — the max entry in the matrix is the graph's diameter; the min of max-per-row is the radius. Floyd-Warshall gives them in O(V³).
  • Detecting negative cycles — any negative diagonal entry signals a node trapped in a negative cycle.
  • Regex-to-NFA conversion (Kleene's algorithm) — same triple-loop pattern; the matrix entries become regular expressions instead of distances.

When to reach for something else

  • Single source on a non-trivial graph — use Dijkstra. O((V + E) log V) is far better than O(V³).
  • Sparse graph, need all pairs — use Johnson's algorithm: one Bellman-Ford to reweight, then V Dijkstras. O(V·E·log V) instead of O(V³).
  • V > a few thousand — O(V³) hits the wall. V = 5000 means ~10¹¹ operations.

Pros

  • Three lines of code — the inner loop is one line. Hard to get wrong, easy to verify.
  • Handles negative edges — and detects negative cycles via the diagonal-entry check.
  • No data structures beyond a matrix — no heaps, no priority queues, no queues. Just two arrays.
  • Cache-friendly — the inner loop is a tight matrix scan; modern CPUs love this and can SIMD-vectorise it.
  • Generalises — the (min, +) semiring becomes (OR, AND) for reachability or (regex-union, regex-concat) for finite-automata problems.

Cons

  • O(V³) — V = 1000 is already a billion operations; V = 10000 is hopeless.
  • O(V²) memory — same wall: a 5000-node matrix of doubles is 200 MB.
  • Computes all V² pairs even if you only need one — wasteful for single-source queries.
  • No early exit — runs through every (k, i, j) triple even when the answer stabilises early.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

floyd-warshall.ts
// Floyd-Warshall — all-pairs shortest paths in O(V³).
// Handles negative edges; detects negative cycles via diagonal.
function floydWarshall(weight: number[][]): number[][] {
  const n = weight.length;
  // Copy so we don't mutate the input.
  const dist = weight.map(row => row.slice());

  // Initialise: distance to self is 0, missing edges already ∞.
  for (let i = 0; i < n; i++) dist[i][i] = 0;

  // The triple loop — k MUST be outermost.
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      // Tiny win: skip rows that can't reach k.
      if (dist[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        const through = dist[i][k] + dist[k][j];
        if (through < dist[i][j]) dist[i][j] = through;
      }
    }
  }

  // Negative-cycle check: any negative diagonal entry means
  // that node sits on a negative cycle.
  for (let i = 0; i < n; i++) {
    if (dist[i][i] < 0) throw new Error("negative cycle detected");
  }
  return dist;
}

// To reconstruct paths, keep a `next[i][j]` matrix:
// next[i][j] starts as j (direct edge); update to next[i][k] when k improves dist[i][j].

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why must k be the outermost loop in Floyd-Warshall?

question 02 / 03

How does Floyd-Warshall detect a negative cycle?

question 03 / 03

When does V calls to Dijkstra beat Floyd-Warshall for all-pairs shortest paths?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Graph Algorithms