Název: Hledání nejkratších cest grafem
Překlad názvu: The Shortest Graph's Pahts Finding
Autoři: Jágr, Petr ; Ohlídal, Miloš (oponent) ; Jaroš, Jiří (vedoucí práce)
Typ dokumentu: Bakalářské práce
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Předmětem této bakalářské práce je hledání, porovnání, úprava a implementace vhodných grafových algoritmů vedoucích k nalezení všech nejkratších cest mezi všemi dvojicemi vrcholů v neorientovaných grafech. Pro tento účel jsou využity modifikace již existujících algoritmů a jejich fragmentů tak, aby bylo docíleno co možná nejnižší časové náročnosti výpočtu. Porovnáme si Dijkstrův, Floyd-Warshallův a Bellman-Fordův algoritmus. The aim of this thesis is finding, comparing and implementation of algorithms for finding the shortest paths between each of pairs of nodes in a graph. For this task I use modifications of existing algorithms to achive the lowest time consumption of the computation. Modifications are established on Dijkstra's and Floyd-Warshall's algorithm. We also familiarize with Bellman-Ford algorithm.
Klíčová slova: algoritmus; asymptotické vyjádření složitosti; Bellman-Fordův algoritmus; cesta; Dijkstrův algoritmus; dynamické programování; Floyd-Warshallův algoritmus; genetické algoritmy; heuristické algoritmy; hladové algoritmy; Java; nejkratší cesta; neorientovaný graf; ohodnocený graf; Omega; Omikron; orientovaný graf; paralelní algoritmy; plánování trasy; pravidelný graf; rekurzivní algoritmy; rozděl a panuj; sled; smyčka; souvislý graf; stupeň vrcholu; tah; teorie grafů; Theta; algorithm; asymptotic notation; Bellman-Ford algorithm; complete graph; degree of a vertex; Dijkstra's algorithm; directed graph; divide and conquer algorithms; dynamic programming; Floyd-Warshall algorithm; genetic algorithms; graph teory; greedy algorithms; heuristic algorithms; Java; loop; move; Omega; Omicron; paralel algorithms; path; path planning; recursive algorithms; regular graph; sequence; the shortest path; Theta; undirected graph; weighted graph

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/56214

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


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 > Bakalářské práce