ON THE ALL-PAIRS SHORTEST-PATH ALGORITHM OF MOFFAT AND TAKAOKA

Authors
MEHLHORN K PRIEBE V
Citation
K. Mehlhorn et V. Priebe, ON THE ALL-PAIRS SHORTEST-PATH ALGORITHM OF MOFFAT AND TAKAOKA, Random structures & algorithms, 10(1-2), 1997, pp. 205-220
Citations number
18
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
10
Issue
1-2
Year of publication
1997
Pages
205 - 220
Database
ISI
SICI code
1042-9832(1997)10:1-2<205:OTASAO>2.0.ZU;2-N
Abstract
We review how to solve the all-pairs shortest-path problem in a nonneg atively 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 nonnegatively weighted digraphs. We al so prove that, for a large class of probability distributions, Ohm(n l og n) time is necessary with high probability to compute shortest-path distances with respect to a single source. (C) 1997 John Wiley & Sons , Inc.