Dijkstrov algoritmus

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

Popis samotného algoritmu[upraviť | upraviť zdroj]

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) (pozri údajový 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.

Výpočtová zložitosť[upraviť | upraviť zdroj]

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

Iné projekty[upraviť | upraviť zdroj]