Datensatz

DATENSATZ AKTIONEN

Dieser Datensatz wurde verworfen!DetailsÜbersicht

Verworfen

Zeitschriftenartikel

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

MPG-Autoren

/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;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

Es sind keine frei zugänglichen Volltexte in PuRe verfügbar

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

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

Zusammenfassung

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.