Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
ŠEDA, M.
Originální název
Hledání nejkratších cest
Anglický název
Finding Shortest Paths
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
čeština
Originální abstrakt
Součástí řešení řady praktických problémů je nalezení nejkratších cest mezi všemi dvojicemi zadaných bodů. V teorii grafů k tomuto účelu slouží známý Floyd-Warshallův algoritmus. V příspěvku ukážeme, že nejkratší cesty v případě, kdy všechny spojnice daných bodů jsou ohodnoceny nezápornými čísly, lze v reálných situacích určit efektivněji než F-W algoritmem opakovanou aplikací Dijkstrova algoritmu, budeme-li jej implementovat pomocí binární haldy
Anglický abstrakt
Many practical problems are based on finding shortest paths among all pairs of given points. This problem is usually solved by the Floyd-Warshall algorithm. In this paper is shown that in the case when all edges have nonnegative weights it is possible to solve it by more efficient approach based on a "repeated" application of the Dijkstra algorithm if it is implemented using the binary heap date structure.
Klíčová slova v angličtině
all-pairs shortest path problem, binary heap
Autoři
Rok RIV
2003
Vydáno
1. 9. 2003
Nakladatel
TU v Liberci
Místo
Liberec
ISBN
80-7083-733-0
Kniha
Sborník konference kateder automatizace a kybernetiky PRINCIPIA CYBERNETICA ‘03
Strany od
133
Strany do
138
Strany počet
6
BibTex
@inproceedings{BUT13225, author="Miloš {Šeda}", title="Hledání nejkratších cest", booktitle="Sborník konference kateder automatizace a kybernetiky PRINCIPIA CYBERNETICA ‘03", year="2003", pages="6", publisher="TU v Liberci", address="Liberec", isbn="80-7083-733-0" }