On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka
Lists
Only you see this
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...