Finding the hidden path: time bounds for allpairs shortest paths (1993)by D.R. Karger, D. Koller, and S. J. Phillips
Abstract:
We investigate the allpairs shortest paths problem in weighted graphs. We present an algorithmthe Hidden Path Algorithmthat 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 pathcomparison based algorithm for the allpairs shortest paths problem. Pathcomparison 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.
Download Information
D.R. Karger, D. Koller, and S. J. Phillips (1993). "Finding the hidden path: time bounds for allpairs shortest paths." SIAM Journal on Computing, 22(6), 11991217.
Full version of paper in FOCS '91.


Bibtex citation
@article{Karger+al:93,
author = "D.R. Karger and D. Koller and S. J. Phillips",
title = "Finding the hidden path: time bounds for allpairs
shortest paths",
journal = "SIAM Journal on Computing",
volume = "22",
number = "6",
pages = "11991217",
note = "Full version of paper in FOCS '91",
year = "1993",
}
full list
