Programming

Floyd–Warshall

It is not a road-trip calculator. It is a universal matrix inversion engine: swap out two algebraic symbols, and the exact same four-line loop morphs from pricing shortest paths into counting quantum walks, proving reachability, or decoding hidden Markov trellises.

Four lines and 10^9 updates solve all-pairs distances for 1,000 towns: how three nested loops sweep a network.

Mission 21about 8 min

Compute all-pairs shortest paths across a network in four lines of code by sweeping intermediate waypoints.

  1. Call the effect of relaxing intermediate vertex k on direct distances before stepping the matrix
  2. Step the SemiringMatrix through k=1 to 4 to watch path closures evolve across all pairs simultaneously
  3. Take the boss round bet on why swapping arithmetic definitions solves four different computer science problems

After thisYou will compute transitive closures, widest bottlenecks, and matrix inverses in closed semirings.

Short on timeStep through the SemiringMatrix to see how intermediate vertex k updates the full 4×4 grid in place.

Four Lines, Four Universes

3 minthe hook

A thousand towns put updates inside one triple loop. The same loop answers four different problems, and only the arithmetic changes: , , , .

Here the board is smaller: four towns, five one-way roads, and a tiny grid of numbers. Under standard arithmetic, cell A→D is a distance. Alter two algebraic definitions, and the exact same numbers answer four unrelated branches of computer science.

A --1--> B --1--> D
 \        |        ^
  1       1        1
   \      v        |
    ---> C --------+

The roads form a matrix , where is the cost of traveling directly from to , and a dot marks the absence of a road.

      A  B  C  D
 A    ·  1  1  ·
 B    ·  ·  1  1
 C    ·  ·  ·  1
 D    ·  ·  ·  ·

That grid is the entire input. Focus on cell A→D and consider what value belongs there.

The picture is the sequence of lenses: each round lets paths pass through one more vertex, and every lens either takes the new hub or bypasses it.

Look at cell A→D in the grid. Under (min, +) it closes at 2. Switch to (+, ×) and the same cell becomes 3. What is each arithmetic calculating?

NextWhy does Dijkstra from every vertex fail on networks with negative edge weights?

The Four-Line Ghost

2 minthe trap

Here is the entirety of the algorithm:

for k = 1 … n
  for i = 1 … n
    for j = 1 … n
      R[i][j] ← R[i][j] ⊕ R[i][k] ⊗ R[k][j]

Notice what is absent: no priority queues, no edge pointers, no graph traversals. Nowhere does the code specify what and mean.

Standard teaching obscures this by hardcoding and . That is a single arbitrary choice, and every interpretation the algorithm can manifest lives inside that algebraic substitution.

Running Dijkstra from every vertex costs and refuses negative edges. Bellman–Ford from every vertex costs . These four lines run in , accept negative edges, and never ask what the numbers represent.

NextHow do three nested loops over intermediate waypoint k compute all-pairs distances?

The Kleene Star and Semiring Algebras

2 minthe invariant

A semiring is an algebraic structure with addition and multiplication satisfying four conditions (Golan 1999):

  • is a commutative monoid with identity .
  • is a monoid with identity .
  • Multiplication distributes over addition: .
  • The zero element annihilates under multiplication: .

The four-line loop requires nothing else. Associativity permits regrouping road chains, distributivity allows branching paths at intermediate vertices, and annihilation ensures missing roads contribute nothing.

A closed semiring equips every element with a Kleene star (Kleene 1951):

When the geometric series converges, . For an entire matrix , the triple loop computes the matrix closure , the least solution of (Lehmann 1977). Four choices define the table below:

semiring⊕⊗zeroonethe entry means
cheapest route
number of routes
ORANDfalsetruewhether a route exists
longest route

Each row represents an arithmetic obeying the exact same four axioms. The code executes identically across all four.

NextHow does the closed semiring Kleene star generalize shortest paths to reachability and bottleneck capacity?

Elimination and the Semiring Inverse

2 minthe algebra

The recurrence. Let represent the matrix state after admitting the first vertices as possible intermediates (Warshall 1962; Floyd 1962):

Here equals on the diagonal and elsewhere, representing a zero-length stay. After rounds, .

Round eliminates vertex from remaining paths. A path entering may loop through arbitrarily many times, forming the star .

When addition is idempotent (, as in , , and ), self-loops collapse to . Real addition is non-idempotent (), making each loop a distinct path, where the star becomes the geometric series .

Four readings of this grid. Inspect cell A→D after closure:

readingA→Dthe number is
2the fewest roads on a route
3the most roads on a route
1 (true)whether D is reachable
3how many distinct routes

Under and , cell A→D prints 3, yet they count different concepts: three edges along the longest path versus three distinct paths. Every semiring panel agrees with its row, cell for cell.

Matrix inversion. Over real numbers under on an acyclic graph, the closure is the classic Neumann series:

The four-line loop is simply Gaussian elimination computing a matrix inverse in a semiring (Lehmann 1977). Shortest paths, path counts, connectivity, and longest routes are all the identical matrix inverse.

NextHow does the four-line loop detect negative cycles when diagonal matrix entries drop below zero?

Morphing Arithmetic on a 4×4 Grid

2 minthe simulation

Below is your grid. Start in and drag the slider from 0 to 4. The same four lines run over the same numbers, updating rows and columns through intermediate vertex .

Watch cell A→D through the lenses in as you drag from 0 upward: exactly one off-diagonal cell changes, and under that same cell counts routes.

for k = 1 … n
  for i = 1 … n
    for j = 1 … n
      R[i][j] ← R[i][j] ⊕ R[i][k] ⊗ R[k][j]
semiring (min, +)⊕ = min, ⊗ = +zero +∞one 0
A
B
C
D
A
0
1
1
2
B
∞
0
1
1
C
∞
∞
0
1
D
∞
∞
∞
0

All-pairs closure under (min, +): R after n = 4 rounds.

One 4×4 grid, four arithmetics. Choose a semiring, then drag k from 0 to 4. A dot in the input is the absent road; it reads as +∞, 0, false or −∞ depending on the arithmetic you chose.

1 minboss round

Under (min, +), exactly one off-diagonal cell changes as you drag k from 0 to 4. Which cell updates, and at which round?

Switch to and drag the slider again. Round 2 sets A→D = 2, but round 3 lifts it to 3 because A→B→C→D becomes available once C is admitted. Switch to and the same cell transitions from 0 to 1 at round 2.

NextHow do transitive closure matrices solve compiler data-flow and networking reachability?

The Many Faces of the Closure

2 minsystems

Shortest paths. is Floyd’s 1962 formulation, solving all-pairs distances in cubic time. Negative edge weights are supported; a negative diagonal after round flags a negative cycle.

Reachability. is Warshall’s 1962 transitive closure. Relational databases evaluate graph queries with it, and compiler build tools compute dependency closures.

Maximum-likelihood paths. Viterbi decoding of hidden Markov models uses ; taking logarithms converts it to . The identical recurrence powers speech recognition and genomic parsing.

Capacity and bottleneck. The bottleneck algebra maximizes the minimal edge capacity along a route. This computes maximum-bandwidth paths across communication backbones.

Counting. counts walks. While counting walks in a graph with cycles is polynomial, counting simple paths without repeated vertices is #P-complete (Valiant 1979).

Next missionFixed-Point IterationAt q=0.9999 one digit costs 23,025 steps; at q=0.6736 it takes 5.8: how the cobweb spiral converges to a fixed point.

The Boundary of Convergence: When the Star Diverges

The closure sums over paths of unbounded length, meaning convergence depends on the algebraic properties of the graph:

readingthe closure exists exactly when
no cycle has negative total cost; otherwise the sum runs down forever
no cycle has positive total cost; otherwise the sum runs up forever
the grid has no cycle — otherwise there are infinitely many walks
always; a Boolean cycle adds no new truth

For and , a diagonal entry is unless a cycle pays off, making the star collapse. For , the star is a geometric series that diverges the moment a cycle exists.

The chart below shows path counts under on an acyclic graph versus a cycle.

The same four lines under (+, ×), on two grids: one fixed cell each

02402.557.51012.5m, the longest walk allowedroutes counted, under (+, ×)
acyclic 4-node grid: A→D3-node cycle: A→A

The flat line shows an acyclic graph where the sum terminates at 3 paths. The ascending line shows a three-vertex cycle where every traversal adds walks, diverging without bound.

On dense graphs, Floyd–Warshall’s runtime outperforms running Dijkstra times (). Its simplicity and branchless execution make it exceptionally fast on modern hardware caches.

Attributions

  • Kleene 1951 — the star and the algebra of regular events; the closure reading of §2.
  • Warshall 1962 — A theorem on Boolean matrices: the triple loop for transitive closure, the instance.
  • Floyd 1962 — Algorithm 97: Shortest path: the same loop with weights, the instance.
  • Lehmann 1977 — Algebraic structures for transitive closure: the algebraic path problem, closure by elimination in an arbitrary semiring, and the idempotence conditions it needs.
  • Roy 1959 — Transitivité et connexité: an earlier statement of the same closure.
  • Backhouse and Carré 1975 — Regular algebra applied to path-finding problems: the semiring reading of path problems.
  • Golan 1999 — Semirings and their Applications: the four axioms quoted in §2.
  • Valiant 1979 — counting simple paths is #P-complete, the boundary between this closure and that count.