Přístupnostní navigace
E-application
Search Search Close
Publication detail
ŠEDA, M.
Original Title
Hledání nejkratších cest
English Title
Finding Shortest Paths
Type
conference paper
Language
Czech
Original Abstract
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
English abstract
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.
Key words in English
all-pairs shortest path problem, binary heap
Authors
RIV year
2003
Released
1. 9. 2003
Publisher
TU v Liberci
Location
Liberec
ISBN
80-7083-733-0
Book
Sborník konference kateder automatizace a kybernetiky PRINCIPIA CYBERNETICA ‘03
Pages from
133
Pages to
138
Pages count
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" }