Dijkstrov algoritmus

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 orientovanom grafe 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).

Popis samotného algoritmu

Pre každý vrchol grafu G udržiava algoritmus štyri symboly. Prvým je t(v), ktorý zaznamenáva dĺžku doteraz najkratšej 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). Ďalším symbolom je dvojstavová premenná p(v) (pozri údajový typ), určujúca či je doteraz najkratšia nájdená cesta t konečná alebo ňou nie je. Poslednou potrebnou charakteristikou bude riadiaci vrchol r.

Pred samotným behom je potrebné inicializovať už uvedené 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,
• r = s, teda za riadiaci vrchol zvolíme počiatok.

Samotný algoritmus pozostáva z dvoch opakujúcich sa krokov:

1. Overíme, či sa d, teda cieľ, nestal riadiacim vrcholom . V takom prípade (r = d) algoritmus končí a jeho výsledkom sú s, ..., x(x(x(d))), x(x(d)), x(d), d (čiže najkratšia s – d cesta) a t(d) (jej dĺžka). 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.
2. Nájdeme spomedzi 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) = ∞ (a x(d) = 0), tak je zrejmé, že spojenie s – d neexistuje.

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. Keďže |H| = O(|V|²), výpočtová zložitosť Dijkstrovho algoritmu je O(n²).

Iné projekty

Commons

• Commons ponúka multimediálne súbory na tému Dijkstrov algoritmus