= Solution
Initialize an $n\times n$ array $d$ with $d_{ii}=0$ and $d_{ij}=a_{ij}$ for $i\ne j$. For $k=1,\ldots,n$, replace every entry in place by
$$
d_{ij}\leftarrow\min\{d_{ij},d_{ik}+d_{kj}\}.
$$
This is the <Floyd-Warshall algorithm>. At the start of stage $k$, the induction hypothesis is $d_{ij}=u_{ij}^{(k-1)}$. During that stage, row $k$ and column $k$ do not change: $d_{kk}=0$ and no negative cycle can lower it. Hence the operands $d_{ik},d_{kj}$ remain the stage-start values even with in-place updates. Part (b) proves that after the stage every entry is $u_{ij}^{(k)}$. Induction gives all shortest path lengths after stage $n$. The algorithm uses $n^2$ stored lengths and $O(n^3)$ arithmetic operations, with only a fixed number of loop counters beyond the array.
Back to article page
