Název: Nejkratší cesty v grafu
Překlad názvu: Shortest Paths in a Graph
Autoři: Krauter, Michal ; Křivka, Zbyněk (oponent) ; Masopust, Tomáš (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2009
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Tato práce se zabývá problematikou nejkratších cest v grafu. Hledání těchto cest patří mezi základní problémy teorie grafů s četnými praktickými aplikacemi. Problém hledání nejkratších cest lze rozdělit na dvě skupiny. V první z nich hledáme nejkratší cesty z jednoho konkrétního uzlu do všech ostatních uzlů a v druhé hledáme nejkratší cesty mezi všemi páry vrcholů grafu. U každé skupiny jsou v textu uvedeny principy a algoritmy, které problém řeší. Studovány a popsány jsou jak klasické, tak i nové efektivnější metody. Z každé skupiny jsou vybrány, implementovány a experimentálně porovnány některé algoritmy pro hledání nejkratších cest v grafu. This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.
Klíčová slova: Bellmanův-Fordův algoritmus; Dijkstrův algoritmus; Floydův-Warshallův algoritmus.; grafový algoritmus; Nejkratší cesta; nejkratší cesty mezi všemi vrcholy grafu; all-paris shortest path problem; Bellman-Ford's algorithm; Dijkstra's algorithm; Floyd-Warshall's algorithm.; graph algorithms; Shortest paths; single-source shortest path problem

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/53883

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-588232


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce