All pairs shortest paths using fast matrix multiplication
Uri Zwick, Tel Aviv University, Israel

Several recent algorithms for solving the all pairs shortest paths
(APSP) problem in graphs will be discussed. All these algorithms use
fast algorithms for algebraic matrix multiplication. Among the
algorithms is an O(n^{2.575}) time algorithm for solving the APSP
problem in unweighted directed graphs, and an O(n^\omega) time
algorithm for solving the problem in unweighted undirected graphs,
where \omega<2.376 is the exponent of algebraic matrix multiplication.