Shortest Paths and Matrices

Inner loop of Fischer and Meyer’s 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.)

$\underline{MatrixSquare(A):} \\ \hspace{0.4cm} for\space i ← 1\space to\space n \\ \hspace{1cm} for\space j ← 1\space to\space n \\ \hspace{1.7cm} A^′[i, j] ← 0 \\ \hspace{1.7cm} for\space k ← 1\space to\space n \\ \hspace{2.3cm} A^′[i, j] ← A^′[i, j] + A[i, k] · A[k, j]$ ...