Search⌘ K
AI Features

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 n×nn × n matrix AA with the inner loop of FischerMeyerAPSPFischerMeyerAPSP. (We’ve slightly modified the notation in the second algorithm to make the similarity clearer.)

Algorithm


MatrixSquare(A):for i1 to nfor j1 to nA[i,j]0for k1 to nA[i,j]A[i,j]+A[i,k]A[k,j]\underline{MatrixSquare(A):} \\ \hspace{0.4cm} for\space i ← 1\space to\space n \\ \hspace{1cm} for\space j ← 1\space ...