Hledání nejkratších cest

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

Jazyk výsledku
čeština
Název v původním jazyce
Hledání nejkratších cest
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
Finding Shortest Paths
Popis výsledku anglicky
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 tosolve it by more efficient approach based on a "repeated" application of the Dijkstra algorithm if it is implemented using the binary heap date structure.

Rok uplatnění
2003
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
Sborník konference kateder automatizace a kybernetiky PRINCIPIA CYBERNETICA '03
ISBN
80-7083-733-0
ISSN
—
e-ISSN
—
Počet stran výsledku
6
Strana od-do
133-138
Název nakladatele
TU v Liberci
Místo vydání
Liberec
Místo konání akce
Liberec
Datum konání akce
3. 9. 2003
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—

Podobné výsledky(10)