On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka

Kurt Mehlhorn, Volker Priebe

Abstract

We review how to solve the all-pairs shortest path problem in a non-negatively weighted digraph with n vertices in expected time O(n 2 log n). This bound is shown to hold with high probability for a wide class of probability distributions on non-negatively weighted digraphs. We also prove that for a large class of probability distributions Ω(n log n) time is necessary with high probability to compute shortest path distances with respect to a single source.
BibTeX
@inproceedings{mehlhorn1995all,
  author = {Kurt Mehlhorn and Volker Priebe},
  title = {{On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka}},
  booktitle = {ESA},
  year = {1995},
  doi = {10.1007/3-540-60313-1\_143},
}

Loading related content...

Figure