Detail práce

Hledání nejkratších cest grafem

Bakalářská práce Student: Jágr Petr Akademický rok: 2006/2007 Vedoucí: Jaroš Jiří, doc. Ing., Ph.D.
Název anglicky
The Shortest Graph's Pahts Finding
Jazyk práce
český
Abstrakt

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.

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

Ústav
Ústav počítačových systémů FIT VUT v Brně
Studijní program
Informační technologie
Soubory
Stav
obhájeno, hodnocení E
Obhajoba
27. srpna 2007
Oponent
Ohlídal Miloš, Ing.
Komise
Honzík Jan M., prof. Ing., CSc. (UIFS FIT VUT), předseda
Křena Bohuslav, Ing., Ph.D. (UITS FIT VUT), člen
Kunovský Jiří, doc. Ing., CSc. (UITS FIT VUT), člen
Motyčka Arnošt, doc. Ing., CSc. (Mendelu), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Citace
JÁGR, Petr. Hledání nejkratších cest grafem. Brno, 2007. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2007-08-27. Vedoucí práce Jaroš Jiří. Dostupné z: https://www.fit.vut.cz/study/thesis/4340/
BibTeX 
@bachelorsthesis{FITBT4340,
    author = "Petr J\'{a}gr",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Hled\'{a}n\'{i} nejkrat\v{s}\'{i}ch cest grafem",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2007,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/4340/"
}

Závěrečné práce

Nahoru