Dijkstrův algoritmus

Dijkstrův algoritmus řeší problém hledání nejkratší cesty v grafu s nezápornými vahami hran. Je to základní stavební kámen moderních navigačních systémů (GPS) a směrovacích protokolů v počítačových sítích.

1. Jak algoritmus funguje?

Algoritmus využívá strategii „hladového vyhledávání“ (greedy algorithm). Postupuje následovně:

1. **Inicializace:** Startovnímu uzlu přiřadí vzdálenost 0, všem ostatním uzlům nekonečno ($\infty$). Všechny uzly jsou označeny jako "nenavštívené".
2. **Výběr:** Vybere nenavštívený uzel s aktuálně nejmenší vzdáleností od startu (na začátku je to startovní uzel).
3. **Relaxace hran:** U všech sousedů tohoto uzlu spočítá novou potenciální vzdálenost: //"Pokud půjdu přes tento uzel, bude cesta ke sousedovi kratší než ta, kterou znám doteď?"//
4. **Aktualizace:** Pokud je nová cesta kratší, přepíše původní hodnotu u souseda na tuto novou, nižší hodnotu.
5. **Ukončení:** Jakmile jsou prozkoumáni všichni sousedi vybraného uzlu, uzel se označí jako "navštívený" a algoritmus se vrací ke kroku 2, dokud neprojde celý graf.

2. Vlastnosti a omezení

Optimálnost: Algoritmus vždy najde nejkratší cestu, pokud existuje.
Omezení (Nezáporné váhy): Funguje pouze v grafech, kde jsou váhy hran kladné (např. vzdálenost v km, čas v minutách). Pokud by graf obsahoval záporné váhy (např. cesta, která vám „vydělává“ energii), algoritmus by selhal (v takovém případě se používá Bellman-Fordův algoritmus).
Složitost: Při použití efektivních datových struktur (prioritní fronta) je složitost $O((E + V) \log V)$, kde $V$ je počet vrcholů a $E$ počet hran.

3. Praktické využití

GPS a Mapy: Výpočet nejrychlejší trasy z bodu A do bodu B v silniční síti.
Počítačové sítě (Routing): Protokoly jako OSPF (Open Shortest Path First) používají Dijkstru k nalezení nejlepší cesty pro data v internetu.
Logistika: Plánování rozvozu zboží tak, aby se najelo co nejméně kilometrů.
Hry: Pohled (Pathfinding) nehráčských postav (NPC) k cíli.

4. Srovnání: Dijkstra vs. Ostatní

Algoritmus	Typ grafu	Výsledek
BFS	Neohodnocený (váhy jsou 1)	Nejkratší cesta v počtu kroků.
Dijkstra	Ohodnocený (kladné váhy)	Nejkratší cesta v součtu vah.
A*	Ohodnocený + heuristika	Rychlejší hledání směrem k cíli (používá se ve hrách).

[Image comparing Dijkstra (expanding in circles) and A* (expanding towards target)]

Zajímavost: Edsger Dijkstra prý vymyslel tento algoritmus během 20 minut, když seděl se svou snoubenkou v kavárně. Chtěl ukázat schopnosti nového počítače ARMAC a hledal problém, kterému by rozuměli i lidé mimo obor informatiky – vybral si tedy mapu nizozemských měst.

Zpět na Algoritmy