最短経路は熱帯行列のべき乗である

$m$ に関する帰納法で示す。基底段階 $m = 1$：$(A^{\otimes 1})_{ij} = A_{ij}$ は、高々1本の辺を使う最良の歩道の長さに自明に等しい。帰納段階：$(A^{\otimes m})_{ik}$ が、すべての $k$ について、高々 $m$ 本の辺を使う $i$ から $k$ への最短歩道の長さに等しいと仮定する。このとき $(A^{\otimes(m+1)})_{ij} = (A^{\otimes m} \otimes A)_{ij} = \min_k\big((A^{\otimes m})_{ik} + A_{kj}\big)$ となる。$i$ から $j$ への高々 $m+1$ 本の辺を使う歩道は、すでに高々 $m$ 本の辺しか使っていない（$k = j$、$A_{jj} = 0$ の項でカバーされる）か、$i$ からある頂点 $k$ への高々 $m$ 本の辺の歩道に最後の1辺 $k \to j$ を続けたものに分解できる。このようなすべての $k$ にわたって最小をとると、ちょうど $(A^{\otimes(m+1)})_{ij}$ が得られるので、主張は $m + 1$ でも成り立つ。負の重みの閉路がないため、最短歩道は頂点を繰り返す必要がなく、したがってすべての最短経路は高々 $n - 1$ 本の辺しか使わない。$m = n - 1$ とすれば $(A^{\otimes(n-1)})_{ij}$ がちょうど最短経路距離であることが示され、これは辺の本数ではなく中間頂点を1つずつ固定して同じ量を計算する Floyd–Warshall の漸化式と一致する。