Dijkstrov algoritmus: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
interwiki, typografia |
typografia |
||
Riadok 10:
* ''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.
| |||