最短路径即热带矩阵幂

对 $m$ 作归纳。基础情形 $m = 1$：$(A^{\otimes 1})_{ij} = A_{ij}$ 显然就是至多使用一条边的最优通路长度。归纳步骤：假设对每个 $k$，$(A^{\otimes m})_{ik}$ 都等于至多使用 $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$ 这一项覆盖），要么可以拆分为一条至多 $m$ 条边、从 $i$ 到某个顶点 $k$ 的通路，再加上最后一条边 $k \to j$；对所有这样的 $k$ 取最小值，恰好得到 $(A^{\otimes(m+1)})_{ij}$，故命题对 $m + 1$ 也成立。由于不存在负权回路，最短通路无需重复经过顶点，因此每条最短路径至多使用 $n - 1$ 条边；取 $m = n - 1$ 即得 $(A^{\otimes(n-1)})_{ij}$ 恰为最短路径距离，这与 Floyd–Warshall 的递推式一致——后者通过依次固定中间顶点，而非按边数计数，来计算同一个量。