Premium
On the all‐pairs shortest‐path algorithm of Moffat and Takaoka
Author(s) -
Mehlhorn Kurt,
Priebe Volker
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199701/03)10:1/2<205::aid-rsa11>3.0.co;2-7
Subject(s) - citation , path (computing) , algorithm , physics , combinatorics , mathematics , computer science , library science , programming language
We review how to solve the all‐pairs shortest‐path problem in a nonnegatively 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 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. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 10 , 205–220 (1997)