Shortest Paths and Matrices

Explore the different techniques used to implement the shortest paths and matrices algorithm efficiently.

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.)

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy