Bakalářská práce

Modifikácie Dijkstrovho algoritmu pre hľadanie najkratších ciest

Modification of Dijkstra's algorithm for single-source shortest-path problem

Martin Michal Dyttert
Anotace

Cieľom práce je predstaviť tri grafové algoritmy: Dijkstrov algoritmus, Spirov algoritmus a algoritmus Wilsona a Zwicka. Práca sa zameriava na ich teoretický popis so zdôraznením ich vzájomnej nadväznosti a odlišností. Pre lepšie porozumenie je súčasťou práce implementácia algoritmov. Hlavným prínosom práce je vizualizačný nástroj vo forme webovej stránky, ktorý umožňuje názorne sledovať a porovnať priebeh jednotlivých algoritmov.

Abstract

The aim of this thesis is to present three graph algorithms: Dijkstra's algorithm, Spira's algorithm, and the Wilson-Zwick algorithm. The thesis focuses on their theoretical foundations, emphasizing their mutual relationships and differences. To enhance understanding, the algorithms are also implemented in code. The main contribution of the thesis is a visualization tool, implemented as a web application …více

Klíčová slova
graf SSSP problém Dijkstrov algoritmus Spirov algoritmus algoritmus Wilsona a Zwicka vizualizačný nástroj graph Dijkstra's algorithm Spira's algorithm Wilson-Zwick algorithm visualization tool
Zadání práce
Problém hledání nejkratších cest z daného vrcholu do všech vrcholů orientovaného grafu s nezáporným ohodnocením hran lze řešit s menší složitostí (ve srovnání s Dijkstrovym algoritmem) za předpokladu, že incidenční seznam hran je uspořádaný v neklesajícím pořadí. Cílem bakalářské práce je představit algoritmy [1] a [2]. Textová část práce bude obsahovat kompletní popis algoritmů včetně pseudokódů a ilustrativních příkladů. Součástí práce bude webová aplikace s vizuálním znázorněním průběhu výpočtu obou algoritmů.
Administrativní informace
Práce zkontrolována:
29. 5. 2025 09:51, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
607,3 KB / soubor PDF
Přílohy (2)
Jazyk práce
slovenština slovenština
Termín obhajoby
26. 6. 2025
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

RNDr. Jaromír Plhák, Ph.D., učo 60773
KSUZD FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Informatika

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.