On the all-pairs shortest-path algorithm of Moffat and Takaoka

We review how to solve the all-pairs shortest-path problem in a nonnegatively weighted digraph with n vertices in expected time O(n²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, O(nlog(n)) time is necessary with high probability to compute shortest-path distances with respect to a single source.