All-Pairs Shortest Paths in $O(n^2)$ time with high probability

DOI10.1145/2505988zbMath1281.05126arXiv1105.3770MaRDI QIDQ5395724

Dmitry Sotnikov, Yuval Peres, Uri Zwick, Benjamin Sudakov

Publication date: 17 February 2014

Full work available at URL: https://arxiv.org/abs/1105.3770

zbMATH Keywords

probabilistic analysisshortest paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (6)

Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ On the longest path of a randomly weighted tournament ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time

This page was built for publication: All-Pairs Shortest Paths in $O(n^2)$ time with high probability