TheoremProved

Shortest paths as a tropical matrix power

Statement

Let $A$ be the $(\min,+)$ weight matrix of a directed graph on $n$ vertices with no negative-weight cycles. Let $A^{\otimes m}$ denote the $m$ -fold tropical matrix product of $A$ with itself. Then the entry $(A^{\otimes(n-1)})_{ij}$ equals the length of the shortest path from $i$ to $j$ in the graph. This is exactly the quantity computed by the Floyd–Warshall algorithm, whose recurrence $d_{ij}^{(k)} = \min\big(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\big)$ builds up $A^{\otimes(n-1)}$ one intermediate vertex at a time.

Why is it true?

Entry $(A^{\otimes m})_{ij}$ tracks the length of the best walk from $i$ to $j$ using **at most $m$ edges**, because tropical matrix multiplication is exactly "combine a first leg and a rest-of-the-journey via addition, then keep only the cheapest combination" — precisely Bellman's principle of optimality for shortest paths. Iterating this $n - 1$ times is enough because a shortest simple path in an $n$ -vertex graph never needs more than $n - 1$ edges, so no further tropical squaring can improve the answer.

Proof sketch

By induction on $m$ . Base case $m = 1$ : $(A^{\otimes 1})_{ij} = A_{ij}$ is trivially the length of the best walk using at most one edge. Inductive step: assume $(A^{\otimes m})_{ik}$ equals the length of the shortest walk from $i$ to $k$ using at most $m$ edges, for every $k$ . Then $(A^{\otimes(m+1)})_{ij} = (A^{\otimes m} \otimes A)_{ij} = \min_k\big((A^{\otimes m})_{ik} + A_{kj}\big)$ . Any walk from $i$ to $j$ with at most $m+1$ edges either uses at most $m$ edges already (covered by the $k = j$ , $A_{jj} = 0$ term) or splits as a walk of at most $m$ edges from $i$ to some vertex $k$ followed by one final edge $k \to j$ ; minimizing over all such $k$ recovers exactly $(A^{\otimes(m+1)})_{ij}$ , so the claim holds for $m + 1$ . Since there are no negative-weight cycles, no shortest walk needs to repeat a vertex, so every shortest path uses at most $n - 1$ edges; taking $m = n - 1$ shows $(A^{\otimes(n-1)})_{ij}$ is exactly the shortest-path distance, matching the Floyd–Warshall recurrence, which computes the same quantity by fixing intermediate vertices one at a time instead of edge-counts.

Topics that use this theorem

Tropical geometry

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Diane Maclagan, Bernd Sturmfels (2015). Introduction to Tropical Geometry
Grigory Mikhalkin (2005). Enumerative tropical algebraic geometry in R^2 · arXiv:math/0312530
Imre Simon (1978). Limited subsets of a free monoid · DOI:10.1109/SFCS.1978.21