Shortest Paths and Matrices

Inner loop of Fischer Meyer all-pairs shortest paths

There is a very close connection (first observed by Shimbel and later independently by Bellman) between computing shortest paths in a directed graph and computing powers of a square matrix. Compare the following algorithm for squaring an $n × n$ matrix $A$ with the inner loop of $FischerMeyerAPSP$. (We’ve slightly modified the notation in the second algorithm to make the similarity clearer.)

$$\begin{gathered} \underset{‾}{MatrixSquare(A):} \\ fori\leftarrow 1ton \\ forj\leftarrow 1ton \\ {A}^{\text{′}}[i,j]\leftarrow 0 \\ fork\leftarrow 1ton \\ {A}^{\text{′}}[i,j]\leftarrow A^{\text{′}}[i,j]+A[i,k \end{gathered}$$ ...