Đường đi ngắn nhất là một lũy thừa ma trận nhiệt đới

Chứng minh bằng quy nạp theo $m$. Cơ sở $m = 1$: $(A^{\otimes 1})_{ij} = A_{ij}$ hiển nhiên là độ dài đường đi tốt nhất dùng nhiều nhất một cạnh. Bước quy nạp: giả sử $(A^{\otimes m})_{ik}$ bằng độ dài đường đi ngắn nhất từ $i$ đến $k$ dùng nhiều nhất $m$ cạnh, với mọi $k$. Khi đó $(A^{\otimes(m+1)})_{ij} = (A^{\otimes m} \otimes A)_{ij} = \min_k\big((A^{\otimes m})_{ik} + A_{kj}\big)$. Bất kỳ đường đi nào từ $i$ đến $j$ với nhiều nhất $m+1$ cạnh hoặc đã dùng nhiều nhất $m$ cạnh (được bao phủ bởi số hạng $k = j$, $A_{jj} = 0$), hoặc tách thành một đường đi nhiều nhất $m$ cạnh từ $i$ đến một đỉnh $k$ nào đó rồi thêm một cạnh cuối $k \to j$; lấy giá trị nhỏ nhất trên mọi $k$ như vậy khôi phục đúng $(A^{\otimes(m+1)})_{ij}$, vậy khẳng định đúng với $m + 1$. Vì không có chu trình trọng số âm, không đường đi ngắn nhất nào cần lặp lại một đỉnh, nên mọi đường đi ngắn nhất dùng nhiều nhất $n - 1$ cạnh; lấy $m = n - 1$ cho thấy $(A^{\otimes(n-1)})_{ij}$ chính xác là khoảng cách đường đi ngắn nhất, khớp với công thức truy hồi Floyd–Warshall, vốn tính cùng đại lượng đó bằng cách cố định lần lượt từng đỉnh trung gian thay vì đếm số cạnh.