On the all-pairs shortest-path algorithm of Moffat and Takaoka
Kurt Mehlhorn, Volker Priebe · Random Structures and Algorithms · 1997
We review how to solve the all-pairs shortest-path problem in a nonnegatively weighted digraph with n vertices in expected time O(n2 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)