Warshall's Algorithm: Transitive Closure

Given a directed graph, the transitive closure is a boolean matrix R* where

R*[i][j] = 1 ⟺ there exists a directed path (of any length) from i to j.

The adjacency matrix only answers "is there an edge i → j?" — the closure answers "is there a route?". It's the all-pairs version of a reachability query, useful for precomputing reaches(i, j) so that later queries cost O(1): dependency analysis, dead-code detection, database query optimization, deciding whether one state of a machine can ever lead to another.

You could run a DFS/BFS from every vertex — V traversals at O(V + E) each. Warshall's algorithm computes the same thing with three tiny nested loops and no graph traversal at all, which also generalizes beautifully to shortest paths (Floyd's algorithm, next topic).

Number the vertices 1..n. Define:

R⁽ᵏ⁾[i][j] = 1 ⟺ there is a path from i to j whose intermediate vertices (strictly between the endpoints) all come from {1, 2, …, k}.

• R⁽⁰⁾ allows no intermediates — it is exactly the adjacency matrix.
• R⁽ⁿ⁾ allows all intermediates — it is the transitive closure we want.

The magic is going from R⁽ᵏ⁻¹⁾ to R⁽ᵏ⁾. A path that's allowed to use k either:

1. doesn't use k — then it was already counted in R⁽ᵏ⁻¹⁾[i][j], or
2. uses k exactly once — then it splits into i → k and k → j, both avoiding k internally.

In words: "i reaches j, possibly via k, iff it already could — or it reaches k and k reaches j."

A practical reformulation (used by the visualization): for each k and each row i, if R[i][k] = 1 then OR row k into row i — everything k reaches, i now reaches too. One row-OR per (k, i) pair; with bitsets this is how the fast implementations work.

The digraph has edges 1→2, 2→4, 4→1, 4→3 — a cycle 1→2→4→1 with a tail to 3. Step forward and backward with the ← / → arrow keys or the buttons below.

What to watch:

• R⁽⁰⁾ starts as the adjacency matrix. For each k (the cyan row), every row i with R[i][k] = 1 absorbs row k — newly set cells flash green.
• At k = 4 the big bang happens: row 4 is rich (4 reaches 1, 2, 3, and itself), and both 1 and 2 reach 4 — so rows 1 and 2 fill up completely.
• Vertices on the cycle even reach themselves (R[1][1] = 1 via 1→2→4→1), while row 3 stays all-zero — vertex 3 has no outgoing edges, so it reaches nothing.

Three nested loops, one boolean update — that's the whole algorithm. The k loop must be outermost: it controls which intermediates are allowed, and the i/j loops sweep the matrix for each new allowance. (Swapping the loops is the classic bug — it produces wrong answers because row k may not be finalized when other rows try to use it.) The C++ tab also shows the bitset version that speeds this up 60× in practice.

Three nested loops over n = V vertices, with O(1) work inside:

• Time: Θ(V³) — completely independent of the number of edges; the structure is so regular that there are no branches to be lucky with.
• Space: Θ(V²) for the matrix. The update can be done in place — using R⁽ᵏ⁾ cells while still computing R⁽ᵏ⁾ is harmless here, because setting a bit can never unset anything (the OR only grows).

Bitset speedup: storing each row as a machine-word bitset turns the inner j loop into row[i] |= row[k] — V/64 word operations — for Θ(V³ / 64) total. That makes V = 2000 entirely practical.

Versus repeated traversals: V DFS runs cost O(V·(V + E)), which beats Θ(V³) on sparse graphs — but Warshall wins on density, on simplicity, and as the gateway to Floyd's algorithm.