We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices with edge weights chosen independently and uniformly at random from [0,1] is O(n²), in expectation and with high probability. This resolves a long standing open problem.

Joint work with Y. Peres, D. Sotnikov and U. Zwick