6.3 Relaxace

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

Pozorování 6.3

Dijkstrův algoritmus si nyní zobecníme.

Připustíme obecné ohodnocení hran.
Místo otevřeného vrcholu s nejmenší hodnotou $h(v)$ vybereme libovolný vrchol $v$ s konečným ohodnocením $h(v)$, ten relaxujeme a následně uzavřeme.

Může se tedy stát, že uzavřený vrchol bude znovu otevřen.

Stavy vrcholů tedy budou znamenat toto:

otevřený: jeho hodnota se změnila a je potřeba ho relaxovat,
uzavřený: byl relaxován, nevyžaduje akci.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {Relaxace}{$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 \textbf{Vyber otevřený vrchol $v$}
        \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.3: Algoritmus Relaxace

Lemma 6.9 (Vlastnost O (ohodnocení))

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

Zobrazit důkaz

Identicky jako Vlastnost O Dijkstrova algoritmu

$\square$

Lemma 6.10 (Vlastnost D (dosažitelnost))

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

Zobrazit důkaz

Dokážeme stejně jako obdobnou vlastnost BFS s tím rozdílem, že uzavřený vrchol je možné znovu otevřít.

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

Vrchol je poprvé 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$.

Naopak kdyby existoval nějaký dosažitelný, ale neuzavřený vrchol, existoval by ten nejbližší $v$ (co do počtu hran na nejkratší cestě)

Pokud se Relaxace zastaví, znovu otevře již uzavřený vrchol jen konečně-krát, takže stačí uvážit situaci při posledním uzavření předchůdce $v$ na nejkratší cestě.

$\square$

Lemma 6.11 (Vlastnost V (vzdálenost))

Když se výpočet zastaví, je $h(w) = d(v_0, w)$ pro $\forall 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 při jeho poslední relaxaci (tj. než by naposledy uzavřen) muselo platit, že aktuální hodnota $h(w) \gt d(v_0, w)$ (neboť toto platí dokonce až po zastavení Relaxace)

V tom případě ale proběhla změna ohodnocení $h(w)$ a tedy musí platit $h(w) = d(v_0, v) + l((v, w)) = d(v_0, w)$. Spor.

$\square$