All-pairs shortest paths in O ( n 2 ) time with high probability
Yuval Peres, Dmitriy V. Sotnikov, Benny Sudakov, Uri Zwick · Journal of the ACM · 2013
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 from [0,1] is O ( n 2 ), in expectation and with high probability. This resolves a long-standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano [2006]. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O ( n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O (log 2 n ) expected time.