Algoritmus Dijkstra
Dijkstrův algoritmus je grafový algoritmus vytvořený nizozemským vědcem Edsgerem Wybem Dijkstrou (1930–2002). Slouží k vyhledání nejkratší cesty z počátečního uzlu do všech ostatních uzlů ohodnoceného grafu. Poradí si však jen s nezáporným ohodnocením hran. Často se používá v routovacích protokolech, například v algoritmu OSPF (Open Shortest Path First).
Vstupem algoritmu je nezáporně ohodnocený graf a počáteční uzel, výstupem je datová struktura (například pole nebo tabulka) obsahující délky nejkratších cest z počátečního uzlu do ostatních uzlů.
Kroky algoritmu
Vstup: ohodnocený graf G, počáteční uzel s Výstup: asociativní pole D(u), udávající nejkratší vzdálenost mezi uzlem s a uzlem u
- INICIALIZACE:
- Vytvoř množinu uzlů X.
- Do množiny X vlož počáteční uzel s.
- Vytvoř asociativní pole čísel pro každý uzel D(u).
- Inicializuj hodnoty pole D takto:
- pro počáteční uzel s = 0
- pro každý uzel u sousedící s počátečním uzlem s = ohodnocení hrany (s,u)
- pro ostatní uzly = nekonečno
- VÝPOČET:
- Dokud nejsou v množině X všechny uzly grafu G, opakuj:
- Najdi uzel w s minimální hodnotou D(w).
- Přidej uzel w do množiny X.
- Pro každý uzel u sousedící s uzlem w který není
v množině X proveď:
- hodnota D(u) je minimum ze stávající hodnoty a D(w) plus ohodnocení hrany (w,u).
Příklad
Inicializace
Vstupem algoritmu je následující graf, počátečním uzlem s je uzel A.
vstupní ohodocený graf
Všechny kroky v tabulce
Každý řádek tabulky představuje jeden krok algoritmu, ve sloupcích jsou uzly grafu G a množina X. Jednotlivé buňky obsahují hodnotu D(u) odpovídajícího uzlu u ve sloupci. Zkratka „max“ označuje nekonečno.
| A | B | C | D | E | F | množina X |
|---|---|---|---|---|---|---|
| 0 | 10, A | 3, A | 4, A | max | max | A |
| – | 8, C | – | 4, A | 11, C | max | A, C |
| – | 8, C | – | – | 11, C | 11, D | A, C, D |
| – | – | – | – | 11, C | 11, D | A, C, D, B |
| – | – | – | – | – | 11, D | A, C, D, B, E |
| – | – | – | – | – | – | A, C, D, B, E |
Výsledek
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 8, C | 3, A | 4, A | 11, C | 11, D |
Časová složitost
Dijkstrův algoritmus lze naimplementovat s následující asymptotickou složitostí:
Reference
- Dr. Jeane Stynes, Computer Science
- http://www.cs.umd.edu/…s/sld012.htm
- http://www.cse.wustl.edu/…a/img11.html