Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
David R. Karger, Daphne Koller, Steven J. Phillips · SIAM Journal on Computing · 1993
The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm—the Hidden-Paths Algorithm—that finds these paths in time $O(m^ * n + n^2 \log n)$, where $m^ * $ is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra’s algorithm. It is argued 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. An $\Omega (mn)$ lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms of E. W. Dijkstra [Numer. Math., 1 (1959), pp. 269–271] and R. W. Floyd [Comm. ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more general setting.