Publication detail
Finding Shortest Paths
ŠEDA, M.
Czech title
Hledání nejkratších cest
English title
Finding Shortest Paths
Type
conference paper
Language
cs
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
Czech 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.
Keywords in English
all-pairs shortest path problem, binary heap
RIV year
2003
Released
01.09.2003
Publisher
TU v Liberci
Location
Liberec
ISBN
80-7083-733-0
Book
Sborník konference kateder automatizace a kybernetiky PRINCIPIA CYBERNETICA ‘03
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",
month="September",
publisher="TU v Liberci",
address="Liberec",
isbn="80-7083-733-0"
}