Detail práce
Nejkratší cesty v grafu
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.
Nejkratší cesta, grafový algoritmus, nejkratší cesty mezi všemi vrcholy grafu, Dijkstrův algoritmus, Bellmanův-Fordův algoritmus, Floydův-Warshallův algoritmus.
Burget Radek, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Češka Milan, prof. RNDr., CSc. (UITS FIT VUT), člen
Kreslíková Jitka, doc. RNDr., CSc. (UIFS FIT VUT), člen
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS FIT VUT), člen
Sochor Jiří, prof. Ing., CSc. (FI MUNI), člen
@mastersthesis{FITMT7245, author = "Michal Krauter", type = "Diplomov\'{a} pr\'{a}ce", title = "Nejkrat\v{s}\'{i} cesty v grafu", school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}", year = 2009, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/7245/" }