2011/05/19 by Yuval Peres, Peres, Yuval, Dimitry Sotnikov +5
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DS #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.1105.3770
arxiv created 2011/05/19 · openalex publication_date 2011/05/19 · arxiv updated 2011/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n2), 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. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n2), 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(log2n) expected time.