6.2 Dijkstrův algoritmus

1 Úvod 2 Grafy 3 Stromy 4 Kostry 5 Základní grafové algoritmy 6 Nejkratší cesty v ohodnocených grafech 6.1 Nejkratší cesty 6.2 Dijkstrův algoritmus 6.3 Relaxace 6.4 Bellman-Fordův algoritmus 7 Složitost 8 Haldy 9 Randomizace 10 Řazení 11 Dynamické programování Index Literatura

Definice 6.3 (Dijkstrův algoritmus)

Vstup: Orientovaný graf $G = (V, E)$ s kladnými délkami hran $l : E \rightarrow \mathbb{R}^+$ a počáteční vrchol $v_0$.

Výstup: Vzdálenosti z vrcholu $v_0$ do všech vrcholů grafu $G$.

Poznámka 6.2 (Základní myšlenka Dijkstrova algoritmu)

Místo simulace průchodu BFS vlny v lineárním čase vzhledem k délce hran, Dijkstra zpracuje každou hranu v $O(1)$ čase.

Představme si, že v každém původním vrcholu je budík.

Místo krokové simulace vyslání BFS vlny z vrcholu nastavíme budíky následníků na časy, kdy by do nich vlna dorazila (předpokládáme jednotkovou rychlost šíření vlny).

Zjistíme, ve kterém sousedním vrcholu zazvoní první budík.

Podíváme se, jaké hrany z tohoto vrcholu vedou dále, a spočítáme, kdy po nich vlna dorazí do dalších následníků.

Pokud by do nějakého následníka dorazila dříve, než je nastaven jeho budík, nastavíme tento budík na tento lepší čas.

Opět počkáme, v kterém vrcholu zazvoní první budík, a vše opakujeme pro něj.

Toto opakujeme, dokud nezazvoní budíky ve všech vrcholech.Čas nastavený na budíku vrcholu v označíme $h(v)$.

Počáteční hodnota nenastaveného budíku je $h(v) = +\infty$.

Podobně jako při BFS průchodu budeme rozlišovat tři stavy vrcholů:

nenalezené
otevřené (mají nastavené budíky)
uzavřené (jejich budíky už zazvonily)

Pro každý vrchol v vyjma počátečního $v_0$ si budeme pamatovat jeho předchůdce $P(v)$, abychom mohli nejkratší cesty zrekonstruovat.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {Dijkstra}{$G$, $l : E \rightarrow \mathbb{R}^{+}$, $v_0$}
    \FOR { $v$ in $V(G)$ }
        \STATE stav($v$) := nenalezený
        \STATE $h(v)$ := $+\infty$
        \STATE $P(v)$ := $\bot$
    \ENDFOR
    \STATE stav($v_0$) := otevřený
    \STATE $h(v)$ := $0$
    \WHILE { existují nějaké otevřené vrcholy }
        \STATE Vyber otevřený vrchol $v$, jehož $h(v)$ je nejmenší
        \FOR { Pro všechny následníky $w$ vrcholu $v$ }
            \IF { $h(w) \gt h(v) + l((v, w))$ }
                \STATE $h(w)$ := $h(v) + l((v, w))$
                \STATE stav($w$) := otevřený
                \STATE $P(w)$ := $v$
            \ENDIF
        \ENDFOR
        \STATE stav($v$) := uzavřený
    \ENDWHILE
    \RETURN $P$ a $h$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 6.1: Dijkstrův algoritmus

Tvrzení 6.1

Přepočítání ohodnocení $h(w)$ pro všechny následníky $w$ vrcholu $v$ budeme nazývat relaxace vrcholu $v$

Věta 6.1 (Konečnost a správnost Dijkstrova algoritmu)

Dijkstra na grafu s kladnými délkami hran se v konečném čase zastaví a po jeho skončení budou všechny dosažitelné vrcholy v uzavřeny s $h(v) = d(v_0, v)$.

Lemma 6.4 (Vlastnost O (ohodnocení))

Ohodnocení $h(v)$ v průběhu Dijkstra nikdy neroste a je-li konečné, rovná se délce nějakého sledu z $v_0$ do $v$

Zobrazit důkaz

Indukcí podle doby běhu Dijkstra.

Na počátku výpočtu tvrzení určitě platí, protože jediné konečné ohodnocení je $h(v_0) = 0$.

Kdykoliv Dijkstra snižuje ohodnocení $h(w)$, stane se tak relaxací otevřeného vrcholu v s konečným $h(v)$, jehož následníkem je $w$.

Podle indukčního předpokladu tedy existuje $v_0v$-sled délky $h(v)$.

Jeho rozšířením o hranu $vw$ vznikne $v_0w$-sled délky $h(v) + l((v, w))$, což je přesně nová konečná hodnota $h(w)$.

$\square$

Lemma 6.5 (Vlastnost M (monotonie))

V každém kroku výpočtu platí, že $h(z) \le h(o)$ pro $z$ uzavřený vrchol a $o$ otevřený vrchol. Speciálně pak platí, že Dijkstra nikdy neotevře již uzavřený vrchol.

Zobrazit důkaz

Vždy vybereme otevřený vrchol v s nejmenším $h(v)$.

Před relaxací v tedy musí platit $h(z) \le h(v) \le h(o)$ pro libovolný z uzavřený a o otevřený.

Nyní vrchol v relaxujeme:

Pokud $w$ byl uzavřený, nemůže se jeho hodnota změnit, neboť již před relaxací platilo $h(w) \le h(v)$.
Pokud $w$ byl otevřený nebo nenalezený, jeho hodnota se sice může snížit na $h(v) + l(v, w)$, ale nikdy ne pod $h(v)$, takže ani pod $h(z)$ žádného uzavřeného $z$.

Kdybychom otevřeli již uzavřený vrchol $z$, muselo by platit $h(v) + l(v, z) \le h(z)$, což nelze.

$\square$

Lemma 6.6 (Vlastnost D (dosažitelnost))

Když se Dijkstra zastaví, uzavřené jsou právě vrcholy dosažitelné z $v_0$.

Zobrazit důkaz

Dokážeme stejně jako obdobnou vlastnost BFS.

První otevřeným a následně uzavřeným vrcholem je $v_0$.

Vrchol je otevřen, právě když je do té doby nenalezeným následníkem dříve otevřeného vrcholu a tudíž je dosažitelný z $v_0$.

Protože Dijkstra dle Vlastnosti M, nikdy neotevře již uzavřený vrchol, zbytek důkazu je totožný s BFS:

Kdyby tedy existoval nějaký dosažitelný, ale neuzavřený vrchol, existoval by ten nejbližší (co do počtu hran na nejkratší cestě) a to by vedlo ke sporu.

$\square$

Lemma 6.7 (Vlastnost V (vzdálenost))

Když se Dijkstra zastaví, je $h(w) = d(v_0, w)$ pro všechny $w \in V$

Zobrazit důkaz

Inspirujeme se důkazem obdobné vlastnosti BFS. Vrchol $w$ dosažitelný z $v_0$ nazveme špatný, pokud $h(w) \ne d(v_0, w)$.

Z Vlastnosti O víme, že $h(w)$ odpovídá délce nějakého $v_0w$-sledu a tedy $h(w) \gt d(v0, w)$.

Obdobně jako pro BFS ukážeme sporem, že nemůže existovat žádný špatný vrchol, čímž bude důkaz dokončen.

Myšlenka je opět stejná – budeme předpokládat, že nějaké špatné vrcholy existují.
Vybereme si mezi nimi ten „nejbližší“ k $v_0$ a ukážeme, že nemohl být špatný.
Kdyby ale nějaký špatný byl, musel by být i „nejbližší“.

Pro spor předpokládejme, že existují špatné vrcholy.

Víme, že $v_0$ není špatný, protože $h(v_0) = 0 = d(v_0, v_0)$. Buď $w$ špatný vrchol takový, že nejkratší cesta v $G$ z $v_0$ do $w$ používá nejmenší možný počet hran.

Buď $v$ předchůdce $w$ na této cestě z $v_0$.

Kdyby $v$ byl špatný, volili bychom $v$ namísto $w$. Tedy platí $h(v) = d(v_0, v)$.

Vrchol $v$ byl jistě někdy otevřený a později relaxovaný. Při jeho relaxaci byla aktuální hodnota $h(w)$ větší než $d(v_0, w)$ (neboť toto platí dokonce až po zastavení Dijkstra).

V tom případě ale po relaxaci $v$ muselo platit $h(w) = d(v_0, v) + l((v, w)) = d(v_0, w)$. Spor.

$\square$

Lemma 6.8 (Vlastnost sledů v Dijkstrově algoritmu)

Je-li po uzavření vrcholu $v$ algoritmu Dijkstra $h(v)$ konečné pro nějaký vrchol $v$, rovná se délce nejkratší $v_0v$-cesty, která jako vnitřní vrcholy používá pouze uzavřené vrcholy.

Zobrazit důkaz

Indukcí podle $k$ počtu uzavřených vrcholů.

Pro $k = 0$ platí, neboť jediné konečné je $h(v_0) = 0$.

Pro induční krok, kdy relaxujeme a tedy uzavíráme $v$, uvážíme dva případy:

Relaxace $v$ nezměnila $h(w)$. Pak z IP tvrzení platí.
1. Relaxace v změnila $h(w)$. Pak dle Vlastnosti O $h(w)$ odpovídá délce nejkratší $v_0v$-cesty protažené o hranu $(v, w)$.
2. Protože nyní ale je $v$ uzavřený a $v_0v$-cesta (dle IP) používala jako vnitřní vrcholy jen uzavřené vrcholy, platí tato vlastnost i pro $w$.

$\square$

Věta 6.2 (Složitost Dijkstrova algoritmu)

Pokud jsou délky hran kladné, potom Dijkstra nad souvislým grafem o $n$ vrcholech běží v čase $O(n^2)$

Zobrazit důkaz

Inicializace trvá $O(n)$.

Každý vrchol uzavřeme nejvýše jednou.

Vnějším cyklem projdeme nejvýše $n$-krát.

Pokaždé hledáme minimum až z $n$ ohodnocení vrcholů a procházíme až $n$ následníků.

$\square$

Pozorování 6.2

V grafech s malým počtem hran je odhad $O(n^2)$ zbytečně nadhodnocený.

Celkový počet přepočtení ohodnocení $h(w)$ je pouze $O(m)$.

Ale brzdí nás hledání minima: $O(n)$.

Proto pro ukládání ohodnocení použijeme (binární) haldu.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {Dijkstra}{$G$, $l : E \rightarrow \mathbb{R}^{+}$, $v_0$}
    \FOR { $v$ in $V(G)$ }
        \STATE $h(v)$ := $+\infty$
        \STATE $P(v)$ := $\bot$
    \ENDFOR
    \STATE $h(v)$ := $0$
    \STATE $H$ := HeapBuild($V$) uspořádanou podle klíčů $h$
    \WHILE { dokud $H$ neprázdná }
        \STATE $v$ := HeapExtractMin($H$)
        \FOR { Pro všechny následníky $w$ vrcholu $v$ }
            \IF { $w \in H$ \& $h(w) \gt h(v) + l((v, w))$ }
                \STATE $h(w)$ := $h(v) + l((v, w))$
                \STATE $P(w)$ := $v$
                \STATE HeapDecreaseKey($H$, $w$, $h(v) + l((v, w))$)
            \ENDIF
        \ENDFOR
    \ENDWHILE
    \RETURN $P$ a $h$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 6.2: Dijkstrův algoritmus s binární haldou

Věta 6.3 (Složitost Dijkstrova algoritmu s binární haldou)

Časová složitost je $O(|E| \cdot \log{|V|})$

Zobrazit důkaz

Inicializace trvá $O(|V|)$.

Celková složitost řádku s HeapExtractMin bude $O(|V| \cdot \log{|V|})$.

Celková složitost řádku s HeapDecreaseKey bude $O(|E| \cdot \log{|V|})$ neboť počet volání operace HeapDecreaseKey je nejvýše $|E|$

Vnějším cyklem projdeme nejvýše $n$-krát.

Pokaždé hledáme minimum až z $n$ ohodnocení vrcholů a procházíme až $n$ následníků.

$\square$

Věta 6.4

Dijkstra na grafech s hranami záporných délek bez záporných cyklů může vrcholy otevírat opakovaně a existují grafy, na kterých má exponenciální časovou složitost vzhledem k $n$.