Detail publikace

Hledání nejkratších cest

Š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

ŠEDA, M.

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"
}