# Shortest Paths and Matrices

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

## 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 $n × n$ matrix $A$ with the inner loop of $FischerMeyerAPSP$. (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