Finding the hidden path: time bounds for all-pairs shortest paths (1993)by D.R. Karger, D. Koller, and S. J. Phillips
We investigate the all-pairs shortest paths problem in weighted graphs. We present an algorithm-the Hidden Path Algorithm-that finds these paths in time O(m^* n + n^2 LOGn), where m^* is the number of edges participating in shortest paths. Our algorithm is a practical substitute for Dijkstra's algorithm. We argue that m^* is likely to be small in practice, since m^* = O(n log n) with high probability for many probability distributions on edge weights. We also prove an Omega(m n) lower bound on the running time of any path-comparison based algorithm for the all-pairs shortest paths problem. Path-comparison based algorithms form a natural class containing the Hidden Paths Algorithm, as well as the algorithms of Dijkstra and Floyd. Lastly, we consider generalized forms of the shortest paths problem, and show that many of the standard shortest paths algorithms are effective in this more general setting.
D.R. Karger, D. Koller, and S. J. Phillips (1993). "Finding the hidden path: time bounds for all-pairs shortest paths." SIAM Journal on Computing, 22(6), 1199-1217.
Full version of paper in FOCS '91.
author = "D.R. Karger and D. Koller and S. J. Phillips",
title = "Finding the hidden path: time bounds for all-pairs
journal = "SIAM Journal on Computing",
volume = "22",
number = "6",
pages = "1199--1217",
note = "Full version of paper in FOCS '91",
year = "1993",