12.4 Bellmanův Fordův algoritmus

Bellmanův-Fordův algoritmus

Relaxační algoritmus pro výpočet vzdáleností v grafech s hranami záporných délek, ale bez záporných cyklů.
Namísto haldy (tj . prioritní fronty) jsou otevřené vrcholy ukládány do obyčejné fronty.
Jinými slovy, otevřený vrchol k relaxaci zvolíme vždy jako nejstarší (tedy první) vrchol ve frontě otevřených vrcholů.
Prvně otevřené vrcholy řadíme na konec fronty.

Pro všechny vrcholy v:
    stav(v) := nenalezený; h(v) := +∞; P(v) := ⊥
stav(v0) := otevřený; h(v0) := 0
Vlož v0 do fronty
Dokud je fronta neprázdná:
    Vyjmi první vrchol z fronty a označ ho v
    Pro všechny následníky w vrcholu v:
        Pokud h(w) > h(v) + ℓ((v, w)):
            h(w) := h(v) + ℓ((v, w))
            Pokud stav(w) != otevřený: 
                Přidej w do fronty
            stav(w) := otevřený
            P(w) := v
    stav(v) := uzavřený
Vrať pole vzdáleností h a pole předchůdců P

Fáze výpočtu Bellman-Ford

Nechť \(A_0 = \{v_0\}\).
Fáze \(F_0\) je 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í

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ýznam \(h(v)\) v Bellman-Ford

Význam h(v) v Bellman-Ford

Pro každý nalezený vrchol \(v\) platí na konci fáze \(F_i\), že \(h(v) \leq \ell(S)\), kde \(S\) je nejkratší \(v_0v\)-sled o nejvýše \(i\) hranách.

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) \leq \ell(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) \leq \ell(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) \leq \ell(S')\), hodnota \(h(u)\) se sice mohla změnit, ale ne zvýšit.
Po relaxaci tedy muselo platit \(h(v) \leq h(u) + \ell((u, v)) \leq \ell(S') + \ell((u, v)) = \ell(S)\).

Konečnost Bellman-Ford

Důsledek

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

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 tedy ohodnocení vrcholů již nemohou změnit a algoritmus už žádný vrchol neotevře a zastaví se.

Složitost Bellman-Ford

Věta

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

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

Jednoduchá implementace Bellman-Ford

SimpleBellman-Ford

Algoritmus SimpleBellman-Ford(G, ℓ : E → R, v0)

Pro všechny vrcholy v:
    h(v) := +∞; P(v) := ⊥
h(v0) := 0
Pro i := 1, . . . , n:
    Pro každou hranu (u, v) ∈ E(G):
        Pokud h(v) > h(u) + ℓ((u, v)):
            h(v) := h(u) + ℓ((u, v))
            P(v) := u
Vrať pole vzdáleností h a pole předchůdců P

Vlastnosti algoritmu SimpleBellman-Ford

Obdobně jako pro algoritmus Bellman-Ford bychom pro algoritmus SimpleBellman-Ford mohli dokázat:

Ohodnocení \(h(v)\) nikdy neroste.
Je-li \(h(v)\) konečné, rovná se délce nějakého sledu z \(v_0\) do \(v\).
Pro každý vrchol \(v\) na konci \(i\)-té iterace cyklu na řádku (4) platí, že \(h(v)\) je shora omezeno délkou nejkratšího \(v_0v\)-sledu o nejvýše \(i\) hranách.

Věta

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