Dijkstrov algoritmus
Z Wikipédie
Dijkstrov algoritmus je jedným zo základných algoritmov teórie grafov, jeho primárnym využitím je hľadanie najkratšej cesty v hranovo-ohodnotenom digrafe G = (V, H, c). Tento graf pozostáva z množiny vrcholov V, množiny orientovaných hrán H a funkcie c, ktorá zobrazuje množinu hrán do množiny reálnych čísel. Teda pre ňu platí H → R. Ďalším predpokladom je aby c(h) ≥ 0, pre všetky hrany h z množiny H. Jeho autorom je holandský matematik E. W. Dijkstra a typovo ide o algoritmus najkratšej cesty z jedného vrcholu (počiatok, označme ho aj s) do ostatných, najčastejšie však do jedného konkrétneho (cieľ d).
[úprava] Popis samotného algoritmu
Pre každý vrchol grafu G udržiava algoritmus tri symboly. Prvým je t(v), ktorý zaznamenáva doteraz najkratšiu cestu z počiatku do vrcholu v. Druhým je x(v), ktorý si pamätá predposledný vrchol cesty s – v, teda vrchol pomocou ktorého sa dostaneme do vrcholu v "najrýchlejšie". Tento symbol nie je priamo potrebným pre beh algoritmu, no má svoje využitie pri spätnej konštrukcii cesty z počiatku do cieľa (prípadne hociktorého iného vrcholu množiny V). Posledným symbolom je dvojstavová premenná p(v) (viď Dátový typ), určujúca či je doteraz najkratšia nájdená cesta t konečná alebo ňou nie je. Ďalšou potrebnou charakteristikou bude riadiaci vrchol r.
Pred samotným behom je potrebné inicializovať horeuvedené symboly nasledovne:
- t(v) = ∞, pre všetky v ≠ s; t(s) = 0,
- x(v) = 0, pre všetky v z V,
- p(v) = false, pre všetky v ≠ s; p(s) = true,
a za riadiaci vrchol zvolíme počiatok, teda r = s.
Samotný algoritmus pozostáva z dvoch opakujúcich sa krokov. Prvý z nich kontroluje či náhodou nie je riadiacim vrcholom vrchol d, teda cieľ. V takom prípade algoritmus končí a jeho výsledkom sú t(d), dĺžka najkratšej s – d cesty a postupnosť vrcholov s, ..., x(x(x(d))), x(x(d)), x(d), d, čo je samotná cesta. Ak však podmienka, že riadiacim vrcholom je d neplatí, vykonáme nasledujúci úkon: pre všetky hrany tvaru (r, i) z množiny H, pre ktoré platí, že p(i) = false a t(i) > t(r) + c(r, i) upravíme symbol t(i) na t(r) + c(r, i) a značku x(i) nastavíme na r.
V druhom kroku nájdeme zo všetkých dočasne označených vrcholov v (platí pre ne p(v) = false) taký, ktorého t(v) je najmenšie. Tento vrchol prehlásime za nový riadiaci a jeho značku p(v) nastavíme na true, čo bude znamenať, že t(v) skutočne označuje najkratšiu cestu z vrcholu s do vrcholu v. Ak by nastala situácia, že vrcholov s minimálnym t je viac, môžeme vybrať ľubovoľný z nich. Ďalej pokračujeme vo výpočte prvým krokom.
Ak na konci výpočtu obsahuje t(d) nekonečno (a x(d) = 0), tak je zrejmé, že spojenie s – d neexistuje.
[úprava] Výpočtová zložitosť
Vo všetkých behoch prvého kroku sa vykoná maximálne |H| = m operácií, keďže každú hranu použijeme nanajvýš raz. V druhom kroku stačí prezrieť maximálne |V| = n vrcholov. Výpočtová zložitosť Dijkstrovho algoritmu je teda O(n2).