Daphne Koller

Papers

Daphne Koller Publications

Finding the hidden path: time bounds for all-pairs shortest paths (1993)

by D.R. Karger, D. Koller, and S. J. Phillips

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

Download Information

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.

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 all-pairs
                 shortest paths",
  journal =      "SIAM Journal on Computing",
  volume =       "22",
  number =       "6",
  pages =        "1199--1217",
  note  =        "Full version of paper in FOCS '91",
  year =         "1993",
}

full list