====== 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 ^
| [[it_encyklopedie:bfs|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.

[[it_encyklopedie:algoritmus|Zpět na Algoritmy]]