All-Pairs Distances by Admitting Intermediates
The single-source algorithms each grow one distance label at a time. Floyd–Warshall grows the entire distance matrix at once, using a different bookkeeping trick: instead of asking which edge to scan next, it asks which node a path is now allowed to pass through.
Start with the dense relaxation matrix \(A = I \oplus W\) — zero on the diagonal, each arc weight, \(\infty\) everywhere else — and admit intermediate nodes one at a time. When node \(k\) is admitted, every pair \((i, j)\) gets one question:
Is routing \(i \to k \to j\) shorter than the route I already have?
That question is the same min-plus relaxation as everywhere else, only re-indexed:
\[D[i][j] \;\leftarrow\; \min\bigl(D[i][j],\; D[i][k] + D[k][j]\bigr).\]
After all \(n\) nodes have been admitted, the matrix is the tropical closure \(W^*\) — every entry is an all-pairs shortest distance. For the paper’s six-node graph that is exactly \(A^3\), the matrix the matrix-powers view converges to from the other direction.
Add along a path. Take the minimum across alternatives. Floyd–Warshall just schedules those comparisons by which node sits in the middle.
The explorer is a single self-contained HTML file. It runs entirely in your browser with no server, no network, and no dependencies — so the Download offline HTML link above gives you the same artifact to keep and open directly from disk.
What you can do
- Step or play Floyd–Warshall layer by layer on the paper graph: each layer admits one intermediate node — the highlighted row and column — and the two highlighted addends \(D[i][k]\) and \(D[k][j]\) show the relaxation as it happens.
- Watch the matrix converge to the closure \(W^*\), then read any all-pairs distance straight off a cell (for example, \(D[S][T] = 6\) via \(S \to B \to D \to T\)).
- Run two paths to the closure side by side: admitting intermediates one at a time (\(O(n^3)\)) versus repeated squaring of \(A = I \oplus W\) (\(O(n^3 \log n)\)). Different schedules, the same destination — both land on the identical \(W^*\).
- Switch to the negative-cycle demo and watch a diagonal entry \(D[i][i]\) go negative: the structural signal that a closed walk through \(i\) has negative cost, so no finite all-pairs distances exist.
Supporting information
This page is supporting information for the tropical-algebra paper When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation (Section 4 and Appendix A). It is designed to remain usable offline and is archived on Zenodo alongside the paper, where the five explorers ship together as a downloadable bundle.