All-Pairs Shortest Paths in O(n

Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick

Browse the full FOCS paper archive.