Detail publikace

Hledání nejkratších cest

ŠEDA, M.

Český název

Hledání nejkratších cest

Anglický název

Finding Shortest Paths

Typ

Stať ve sborníku v databázi WoS či Scopus

Jazyk

cs

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 anglicky

all-pairs shortest path problem, binary heap

Vydáno

2003-09-01

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–do

133–

Počet stran

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