Item

ITEM ACTIONS

This item is discarded!DetailsSummary

Discarded

Journal Article

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

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45222

Priebe, Volker
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.

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.