Shortest Paths and Matrices
Understand the relationship between shortest path computations and matrix multiplication. Learn the Fischer Meyer algorithm and its similarities to matrix squaring, explore faster algorithms like Strassen's for matrix multiplication, and grasp advanced methods for computing all-pairs shortest paths in graphs, improving your problem-solving in C++.
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
...