6.4 Bellman-Fordů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

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {BellmanFord}{$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$
    \STATE \textbf{ Vlož $v_0$ do fronty }
    \WHILE { \textbf{dokud je fronta prázdná } }
        \STATE \textbf{ Vyjmi první vrchol z fronty a označ ho $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))$
                \IF { \textbf{ stav($w$) není otevřený } }
                    \STATE \textbf{ Přidej $w$ do fronty }
                \ENDIF
                \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.4: Bellman-Fordův algoritmus

Definice 6.4 (Fáze výpočtu `Bellman-Ford`)

Nechť $A_0 = \{ v_0 \}$

Fáze $F_0 =$ otevření počátečního vrcholu $v_0$, čili všech prvků množiny $A_0 = \{ v_0 \}$

$A_i$ je množina vrcholů, které byly otevřeny při relaxování vrcholů z množiny $A_{i-1}$

Vytvoření množiny vrcholů $A_i$ se nazývá fáze $F_i$

Pozorování 6.4

Pokud se změní hodnota uzavřeného vrcholu, je znovu otevřen.

Hodnota otevřeného vrcholu se může změnit vícekrát, dříve než je vyjmut z fronty, relaxován a uzavřen.

Během výpočtu může tedy daný vrchol postupně patřit do více $A_i$.

Věta 6.5 (Vlastnost 1)

Pro každý nalezený vrchol $v$ platí na konci fáze $F_i$, že $h(v) \le l(S)$ kde $S$ je nejkratší $v_{0}v$-sled o nejvýše $i$ hranách.

Zobrazit důkaz

Tvrzení dokážeme indukcí podle $i$.

Pro $i = 0$ tvrzení platí: jediný vrchol dosažitelný z $v_0$ sledem s 0 hranami je $v_0$ sám; $h(v_0) = 0$ a pro ostatní vrcholy $v$ je $h(v) = +\infty$

Dále nechť $i > 0$.

Zvolme nějaký nalezený vrchol $v$ na konci fáze $F_i$.

Označme $S$ nejkratší $v_0v$-sled o nejvýše $i$ hranách.

Dále označme $e(S)$ počet hran v sledu $S$.Pokud $e(S) < i$, platilo $h(v) \le l(S)$ už na konci předchozí fáze $F_{i-1}$ a jelikož ohodnocení vrcholů nerostou, platí nadále.

Pokud $e(S) = i$, označme $uv$ jeho poslední hranu a $S'$ podsled z $v_0$ do $u$.

Na konci fáze $F_{i-1}$ je z indukce $h(u) \le l(S')$.

Na tuto hodnotu muselo být h(u) nastaveno nejpozději ve fázi $F_{i-1}$, čímž byl vrchol u otevřen.

Nejpozději ve fázi $F_i$ proto musel být vrchol $u$ relaxován.

Na začátku relaxace muselo stále platit $h(u) \le l(S')$, hodnota $h(u)$ se sice mohla změnit, ale ne zvýšit.

Po relaxaci tedy muselo platit $h(v) \le h(u) + l((u, v)) \le l(S') + l((u, v)) = l(S)$.

$\square$

Důsledek 6.2 (Konečnost Bellman-Fordova algoritmu)

Nechť $G = (V, E)$ a $n = |V|$. Pokud $G$ neobsahuje záporné cykly, po fázi $F_n$ se Bellman-Ford zastaví.

Zobrazit důkaz

Po fázi $F_{n−1}$ jsou ohodnocení všech vrcholů shora omezena délkami nejkratších cest, protože nejkratší cesty mají nejvýše $n − 1$ hran.

Ve fázi $F_n$ se se tedy ohodnocení vrcholů již nemohou změnit a algoritmus už žádný vrchol neotevře a zastaví se.

$\square$

Věta 6.6 (Složitost Bellman-Fordova algoritmu)

V grafu bez záporných cyklů nalezne Bellman-Fordův algoritmus všechny vzdálenosti z vrcholu $v_0$ v čase $O(|V| \cdot |E|)$

Zobrazit důkaz

Podle předchozího důsledku se po $|V|$ fázích algoritmus zastaví a podle Vlastnosti 2 o dosažitelnosti vrcholů a Vlastnosti 3 o významu $h(v)$ na konci relaxačního algoritmu vydá správný výsledek.

Během jedné fáze je přitom každý vrchol relaxován nejvýše jednou, takže celá fáze dohromady trvá $O(|E|)$.

$\square$

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {SimpleBellmanFord}{$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$
    \FOR { $i$ := $1, ..., n$ }
        \FOR { Pro každou hranu $(u, v) \in E(G)$ }
            \IF { $h(v) \gt h(u) + l((u, v))$ }
                \STATE $h(v)$ := $h(u) + l((u, v))$
                \STATE $P(v)$ := $u$
            \ENDIF
        \ENDFOR
    \ENDFOR
    \RETURN $P$ a $h$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 6.5: Jednoduchý Bellman-Fordův algoritmus

Věta 6.7

Algoritmus SimpleBellman-Ford je korektní a pracuje v čase $O(|V| \cdot |E|)$