host ::
přihlásit
Digitální repozitář
Hledej
Nový záznam
Nápověda
O repozitáři
Hlavní stránka
>
Vysokoškolské kvalifikační práce
>
Bakalářské práce
> Hledání nejkratších cest grafem
Informace
Soubory
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-239264
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
Záznam vytvořen dne 2016-06-03, naposledy upraven 2022-09-04.
Podobné záznamy
Není přiložen dokument
Exportovat ve formátu
DC
,
NUŠL
,
RIS
Sdílet