All-Pairs Shortest Paths in $O(n^2)$ time with high probability

Yuval Peres, Dimitry Sotnikov, Benny Sudakov +1

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random…