12.3 Relaxační algoritmy

Hrany s nulovými, či zápornými délkami

Samotné záporné hrany problém nezpůsobují, pokud v grafu nevznike záporný cyklus. V takovém případě není definován nejkratší sled, protože ke každému sledu existuje sled ještě kratší.
Pokud tedy graf má záporné hrany, ale neobsahuje záporný cyklus, lemma o zjednodušení sledů a jeho důsledky platí.

Fakt (bez důkazu)

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

Lemma (o zjednodušování sledů 2)

Lemma o zjednodušování sledů 2

Uvažujme orientovaný graf se zápornými délkami hran bez záporných cyklů. Pak pro každý \(uv\)-sled existuje \(uv\)-cesta stejné nebo menší délky.

Algoritmus Relaxace

Porovnáme-li Jarníkův algoritmus s Dijkstrovým, zjistíme, že se liší pouze v definici klíčů prvků haldy a následně tedy i v aritmetickém výrazu pro relaxaci.
Oba patří do třídy tzv. relaxačních algoritmů.

Algortimus Relaxace

Zobecnění Dijkstrova algoritmu, které připouští obecné ohodnocení hran.
Druhé zobecnění bude spočívat v tom, že 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 stát, že uzavřený vrchol bude znovu otevřen.
Stavy tedy znamenají:
Otevřený - hodnota vrcholu se změnila a je potřeba ho relaxovat.

Uzavřený - vrchol byl relaxován.

Pro všechny vrcholy v:
    stav(v) := nenalezený
    h(v) := +∞; P(v) := ⊥
stav(v0) := otevřený
h(v0) := 0
Dokud existují otevřené vrcholy:
    v := nějaký otevřený vrchol
    Pro všechny následníky w vrcholu v: // relaxace v
        Pokud h(w) > h(v) + ℓ((v, w)):
            h(w) := h(v) + ℓ((v, w))
            stav(w) := otevřený
            P(w) := v
    stav(v) := uzavřený
Vrať pole vzdáleností h a pole předchůdců P

Vlastnosti algoritmu Relaxace

Následující 3 vlastnosti platí pro jakoukoli strategii výběru otevřených vrcholů pro relaxaci:

Vlastnost O: Ohodnocení \(h(v)\) nikdy neroste. Je-li \(h(v)\) konečné číslo, rovná se délce nějakého sledu z \(v_0\) do \(v\).
Vlastnost D: Pokud se výpočet zastaví, uzavřené jsou právě vrcholy dosažitelné z \(v_0\).
Vlastnost V: Pokud se výpočet zastaví, \(h(v)\) uzavřeného vrcholu je rovno vzdálenosti \(d(v_0, v)\).

Vlastnost O (ohodnocení)

Ohodnocení \(h(v)\) nikdy neroste. Je-li \(h(v)\) konečné číslo, rovná se délce nějakého sledu z \(v_0\) do \(v\).

Důkaz (stejný jako u Dijkstra)

Indukcí podle doby běhu algoritmu.
Na počátku výpočtu tvrzení určitě platí, protože jediné konečné ohodnocení je \(h(v_0) = 0\).
Kdykoliv algoritmus 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) + ℓ((v, w))\), což je přesně nová konečná hodnota \(h(w)\).

Vlastnost D (dosažitelnost)

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

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ím 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žší“ vrchol \(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ě.

Vlastnost V (vzdálenost)

Pokud se výpočet zastaví, je \(h(w) = d(v_0, w)\) pro všechny \(w \in V\).

Důkaz (téměř stejný jako u Dijkstra)

Vrchol \(w\) dosažitelný z \(v_0\) nazveme špatný, pokud \(h(w) \ne d(v0, w)\). Z Vlastnosti O víme, že \(h(w)\) odpovídá délce nějakého \(v_0w\)-sledu a tedy \(h(w) > d(v_0, w)\).

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 jej mí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ž byl naposledy uzavřen) muselo platit, že aktuální hodnota \(h(w)\) byla větší než \(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) + ℓ((v, w)) = d(v_0, w)\). Spor.