Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
ŠEDA, M.
Originální název
An Efficient Algorithm for All-Pairs Shortest Paths Problem
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
angličtina
Originální abstrakt
The All-Pairs Shortest Paths Problem that finds shortest paths between all pairs of vertices in a connected weighted graph is usually solved by the Floyd-Warshall algorithm based on dynamic programming approach. In this paper, we propose a 'Repeated' Dijkstra algorithm based on a binary heap data structure and show that, for graphs with nonnegative weights, it has lower time complexity than the classical Floyd-Warshall algorithm
Klíčová slova v angličtině
shortest path, dynamic programming, binary heap
Autoři
Rok RIV
2002
Vydáno
1. 9. 2002
Nakladatel
MARQ
Místo
Ostrava
ISBN
80-85988-77-1
Kniha
Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002
Strany od
121
Strany do
126
Strany počet
6
BibTex
@inproceedings{BUT10546, author="Miloš {Šeda}", title="An Efficient Algorithm for All-Pairs Shortest Paths Problem", booktitle="Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002", year="2002", pages="6", publisher="MARQ", address="Ostrava", isbn="80-85988-77-1" }