### All-pairs shortest paths in $O(n^{2})$ time with high probabilityAll-pairs shortest paths in $O(n^{2})$ time with high probability

Access Restriction
Subscribed

 Author Peres, Yuval ♦ Sotnikov, Dmitry ♦ Sudakov, Benny ♦ Zwick, Uri Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Shortest paths ♦ Probabilistic analysis Abstract We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-09-04 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 4 Page Count 25 Starting Page 1 Ending Page 25

#### Open content in new tab

Source: ACM Digital Library