All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

Uri Zwick

We present two new algorithms for solving the {\em All Pairs Shortest Paths} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.…