All-Pairs Shortest Paths in O(n²) Time with High Probability

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Peres, Y, Sotnikov, D, Sudakov, B, Zwick, U
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Data structures
graph algorithms
Harmonic analysis
Heuristic algorithms
Probabilistic logic
random graphs
Random variables
shortest paths
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. 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:0272-5428
DOI:10.1109/FOCS.2010.69