Shortest Paths and Matrices
Understand how all-pairs shortest paths in directed graphs relate to matrix multiplication. Learn Fischer-Meyer's dynamic programming approach and the min-plus algebra concept. Discover faster matrix multiplication methods and their impact on shortest path algorithms, including advanced techniques for special graph types.
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 matrix with the inner loop of . (We’ve slightly modified the notation in the second algorithm to make the similarity clearer.)
Algorithm
...