Shortest Paths and Matrices
Explore the relationship between shortest path algorithms and matrix multiplication through Fischer-Meyer inner loops. Understand how dynamic programming applies to graph problems and the limitations of faster matrix methods for shortest paths.
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 matrix with the inner loop of . (We’ve slightly modified the notation in the second algorithm to make the similarity clearer.)
Algorithm
...