Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Shortest Paths in Matrix Multiplication Time
[Extended Abstract]
verfasst von : Piotr Sankowski
Erschienen in: Algorithms – ESA 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we present an
${\tilde O}(W n^{\omega})$
time algorithm solving single source shortest path problem in graphs with integer weights from the set {–
W
,...,0,...,
W
}, where
ω
< 2.376 is the matrix multiplication exponent. For dense graphs with small edge weights, this result improves upon the algorithm of Goldberg that works in
${\tilde O}(mn^{0.5}{\rm log}W)$
time, and the Bellman-Ford algorithm that works in
O
(
nm
) time.