Publication detail

Hledání nejkratších cest

Š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

ŠEDA, M.

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