Original title: Hledání nejkratších cest grafem
Translated title: The Shortest Graph's Pahts Finding
Authors: Jágr, Petr ; Ohlídal, Miloš (referee) ; Jaroš, Jiří (advisor)
Document type: Bachelor's theses
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: 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; 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

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/56214

Permalink: http://www.nusl.cz/ntk/nusl-601319


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses