An Efficient Algorithm for All-Pairs Shortest Paths Problem

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F02%3APU31529" target="_blank" >RIV/00216305:26210/02:PU31529 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
An Efficient Algorithm for All-Pairs Shortest Paths Problem
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
An Efficient Algorithm for All-Pairs Shortest Paths Problem
Popis výsledku anglicky
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

Rok uplatnění
2002
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002
ISBN
80-85988-77-1
ISSN
—
e-ISSN
—
Počet stran výsledku
6
Strana od-do
121-126
Název nakladatele
MARQ
Místo vydání
Ostrava
Místo konání akce
Krnov
Datum konání akce
9. 9. 2002
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)