# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### On the All-Pairs Shortest-Path Algorithm of Moffat and Takaoka

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K., & Priebe, V. (1997). On the All-Pairs Shortest-Path Algorithm of
Moffat and Takaoka.* Random Structures Algorithms,* *10*,
205-220.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-38C4-F

##### 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, $\Omega(n\log n)$ time is necessary
with high probability to compute shortest-path distances with respect to a
single source.