Bellman-Fordův algoritmus + detekce záporného cyklu (běh)
Dijkstra [L2.4] se na záporné hraně spálila: vrchol $a$ uzavřela se značkou $1$, a opravu přes $b$ na $0$ už nikdy nepřipustila. A v [L2.3] jsme si slíbili algoritmus, který „nic nevymýšlí — relaxuje všechny hrany pořád dokola“. Dnes ten slib splníme: Bellman-Fordův algoritmus (Bellman-Ford algorithm, 1958; nezávisle Moore 1959).
Strategie: žádná strategie
Zkus sám: Dijkstru zradilo předčasné zatrvalnění značky. Jak bys navrhl algoritmus, který se takhle spálit nemůže?
Jednoduše: nic nezatrvalňuj. Žádná množina $R$, žádný výběr minima — prostě procházej všechny hrany grafu pořád dokola a každou zkus relaxovat [L2.3]. Značky smí klesat kdykoliv, takže pozdní oprava (jako $l(a): 1 \to 0$ přes zápornou hranu) projde úplně přirozeně. Relaxaci samotné záporná váha nevadí — to víme z [L2.3]; problém Dijkstry byla strategie pořadí, ne relaxace.
Zkus sám: kolikrát stačí všechny hrany projít? Nápověda: vzpomeň na řetízek z úlohy [L2.3] T01 — informace teče od startu po hranách.
V řetízku $1 \to 2 \to 3 \to 4$ s nejhorším pořadím hran posunul každý průchod „frontu poznání“ o jedinou hranu. To je obecný princip: po $k$-tém průchodu jsou určitě správně značky všech vrcholů, do nichž vede nejkratší cesta s nejvýše $k$ hranami (každý průchod prodlouží zvládnutý úsek každé nejkratší cesty aspoň o jednu hranu — může i o víc, podle pořadí).
A protože cesta v grafu s $n$ vrcholy má nejvýše $n-1$ hran [L2.2], stačí $n-1$ průchodů. (Tohle je intuice; poctivý indukční důkaz — „věta o $k$-té iteraci“ — patří do [L3.7] Korektnost Bellman-Forda. Je to téma ústní zkoušky, žebříček důkazů #4.)
Input: directed graph $G$ without a negative cycle, weights $c : E(G) \to \mathbb{R}$ and node $s \in V(G)$.
Output: vectors $l$ and $p$. For all $v \in V(G)$, $l(v)$ is the length of the shortest path from $s$ and $p(v)$ is the last but one node. If $v$ is not reachable from $s$, then $l(v) = \infty$ and $p(v)$ is undefined.
l(s) := 0; l(v) := ∞ for v ≠ s;
for i := 1 to n − 1 do
for every edge of graph (v, w) ∈ E(G) do
if l(w) > l(v) + c(v, w) then
l(w) := l(v) + c(v, w); p(w) := v;
end
end
end„If an iteration of the main loop terminates without making any changes, the algorithm can be terminated, as subsequent iterations will not make changes any more. The worst case of the algorithm remains unchanged.“ — tedy: jakmile celý průchod nic nezmění, jsme ve fixpointu [L2.3] a lze skončit dřív.
Vnitřní if je znak po znaku stejná relaxace jako u Dijkstry — algoritmy se liší jen pořadím, přesně jak sliboval výhled v [L2.3]. Všimni si také, že váhy jsou $c : E(G) \to \mathbb{R}$ — záporné hrany jsou povolené; zakázaný je jen záporný cyklus [L2.1] (s ním nejkratší cesta ani neexistuje).
Běh na příkladu
Vezměme přesně ten graf, na kterém Dijkstra v [L2.4] selhala ($s \to a$ za $1$, $s \to b$ za $2$, $b \to a$ za $-2$), rozšířený o vrchol $t$ (vlastní příklad). Hrany budeme v každém průchodu zpracovávat v pevném pořadí $(a,t), (s,a), (s,b), (b,a)$ — schválně nešikovném, ať je vidět, jak se značky opravují:
Zkus sám: Dijkstra na tomhle grafu odevzdala $l(a) = 1$. Kde přesně ji Bellman-Ford „opravil“ — a proč to směl udělat?
Hned v prvním průchodu: hrana $(s,a)$ dala $a$ značku $1$, ale o dva kroky později hrana $(b,a)$ našla $2 + (-2) = 0 < 1$ a značku přepsala. Směl to udělat, protože Bellman-Ford žádnou značku neprohlašuje za trvalou — všechny jsou dočasné až do konce běhu. Tomu se říká label-correcting přístup (vs. label-setting Dijkstra, [L2.4]).
Všimni si i druhé strany mince: hrana $(a,t)$ přišla v prvním průchodu „moc brzy“ ($l(a) = \infty$) a $t$ si na značku musel počkat na druhý průchod. Pořadí hran nemění výsledek, jen počet průchodů — na řetízku ze slidu 30 to je úloha [L2.3] T01: nejhorší pořadí 3 průchody, nejlepší 1.
Detekce záporného cyklu
Zkus sám: vstupní specifikace říká „graph without a negative cycle“. Co se stane, když to porušíme a v grafu záporný cyklus dosažitelný z $s$ je?
Algoritmus se nezacyklí — má pevně daných $n-1$ průchodů, takže skončí vždy. Ale značky na cyklu a za ním nikdy nedoklesají: každý oběh záporného cyklu sníží součet, takže fixpoint neexistuje (to je přesně mechanismus „sled levnější než cesta“ z [L2.1]). I po $n-1$ průchodech tedy zbývají hrany, které by relaxace ještě zlepšila.
A to je celý detekční trik: bez záporného cyklu jsou po $n-1$ průchodech hotové všechny nejkratší cesty (mají $\le n-1$ hran), takže žádná hrana už relaxovat nejde. Jde-li nějaká hrana relaxovat i v $n$-tém průchodu, zlepšení nemůže pocházet z žádné cesty — v grafu musí být záporný cyklus.
The Bellman-Ford algorithm can detect a negative cycle that is reachable from vertex $s$ while checking triangular inequality for resulting $l$. There may be negative cycles not reachable from $s$, in such case we add node $s'$ and connect it to all nodes $v$ with $c(s', v) = 0$.
for every edge of graph (v, t) ∈ E(G) do
if l(t) > l(v) + c(v, t) then
error "Graph contains a negative-weight cycle"
end
endHowever, there are better methods for negative cycle detection [Cherkassky&Goldberg 1999].
Zkus sám: proč pomocný vrchol $s'$ s nulovými hranami do všech vrcholů nic nepokazí — nevytvoří sám nový cyklus?
Nevytvoří: do $s'$ žádná hrana nevede, takže $s'$ nemůže ležet na žádném cyklu — všechny cykly grafu (i jejich délky) zůstávají beze změny. Zato z $s'$ je nově dosažitelný každý vrchol (za cenu $0$), takže detekční běh z $s'$ uvidí každý záporný cyklus v grafu, ať se schovává kdekoliv.
Detekce v akci: do našeho grafu přidáme hranu $a \to b$ s váhou $1$ — vznikne cyklus $a \to b \to a$ s délkou $1 + (-2) = -1$. Pořadí hran $(a,t), (s,a), (s,b), (b,a), (a,b)$:
Detekce záporných cyklů není akademická hračka: vrátí se u min-cost flow v kapitole K4 (cycle canceling hledá záporný cyklus právě Bellman-Fordem) a celá zkoušková úloha na ošetření záporných cyklů čeká v [L2.18].
Label-correcting a složitost
Slide 34 shrnuje: „Best known algorithm for SPT without negative cycles.“ Časová složitost je $\mathcal{O}(nm)$ — vnější smyčka $n-1$ průchodů, každý projde všech $m$ hran. Srovnání s Dijkstrou [L2.4]:
| Dijkstra [L2.4] | Bellman-Ford | |
|---|---|---|
| váhy hran | jen $c \ge 0$ | $c \in \mathbb{R}$ (bez záporného cyklu) |
| typ | label-setting (značka trvalá od uzavření) | label-correcting (vše dočasné až do konce) |
| pořadí relaxací | chytré: expanduj minimum | žádné: všechny hrany, $(n-1)\times$ |
| složitost | $\mathcal{O}(n^2)$, resp. $\mathcal{O}(m + n \log n)$ | $\mathcal{O}(nm)$ |
| záporný cyklus | — | umí detekovat ($n$-tý průchod) |
Důkaz korektnosti (věta o $k$-té iteraci a její indukce, slidy 31–33) do téhle lekce schválně nepatří — probereme ho v [L3.7] Korektnost Bellman-Forda; u ústní zkoušky je to častý „dokažte“ kandidát (žebříček důkazů #4).
Pozor: čtyři polopravdy kolem Bellman-Forda- „Detekce najde každý záporný cyklus.“ Přímo jen cykly dosažitelné z $s$. Pro ostatní je potřeba trik ze slidu 34: pomocný vrchol $s'$ a hrany $c(s',v) = 0$ do všech vrcholů.
- „Nulový cyklus se taky chytí.“ Nechytí — a je to správně. Test je ostrá nerovnost $l(t) > l(v) + c(v,t)$: cyklus s délkou $0$ dá po doběhnutí jen rovnosti a nahlášen není (nejkratší cesta s ním existuje). Uvidíš to v úloze T01.
- „Hrana, na které detekce vystřelí, leží na záporném cyklu.“ Nemusí! Porušená trojúhelníková nerovnost dokazuje existenci cyklu kdesi v grafu, nelokalizuje ho (v běhu na detekci záporného cyklu výše vystřelí $(a,t)$, která na cyklu neleží).
- „Se záporným cyklem se algoritmus zacyklí.“ Ne — doběhne vždy ($n-1$ průchodů je pevných), jen vrátí nesmyslné $l$. Právě proto je detekční průchod navíc nutný, chceš-li výsledku věřit.
Key takeaways — L2.12- Bellman-Ford = relaxuj [L2.3] všechny hrany $(n-1)$-krát. Žádné uzavírání → zvládá záporné hrany (záporný cyklus zůstává zakázán [L2.1]). Po $k$ průchodech jsou správně nejkratší cesty s $\le k$ hranami; průchod beze změny = fixpoint, lze skončit dřív.
- Detekce záporného cyklu: pokud v $n$-tém (kontrolním) průchodu jde ještě nějaká hrana relaxovat, graf obsahuje záporný cyklus dosažitelný z $s$. Cykly nedosažitelné z $s$: přidej $s'$ s hranami $c(s',v) = 0$ do všech vrcholů.
- Label-correcting (všechny značky dočasné až do konce), složitost $\mathcal{O}(nm)$ — nejlepší známý algoritmus pro SPT se zápornými hranami; lepší metody existují jen pro samotnou detekci cyklů [Cherkassky&Goldberg 1999].
- Důkaz korektnosti (věta o $k$-té iteraci) → [L3.7]. Téma ústní; žebříček důkazů #4.
Input: directed graph $G$ without a negative cycle, weights $c : E(G) \to \mathbb{R}$ and node $s \in V(G)$.
Output: vectors $l$ and $p$. For all $v \in V(G)$, $l(v)$ is the length of the shortest path from $s$ and $p(v)$ is the last but one node. If $v$ is not reachable from $s$, then $l(v) = \infty$ and $p(v)$ is undefined.
l(s) := 0; l(v) := ∞ for v ≠ s;
for i := 1 to n − 1 do
for every edge of graph (v, w) ∈ E(G) do
if l(w) > l(v) + c(v, w) then
l(w) := l(v) + c(v, w); p(w) := v;
end
end
endIf an iteration of the main loop terminates without making any changes, the algorithm can be terminated, as subsequent iterations will not make changes any more. The worst case of the algorithm remains unchanged.
Study task: run the algorithm on a given graph and write all relaxation iterations.
(Given graph — example from slide 35, source node $A$.) Edge processing order: $(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D)$.
a) Co je v zadání?
Studijní úloha ze slidů: odsimulovat Bellman-Fordův běh na grafu o $n = 5$ vrcholech a vypsat všechny relaxace po průchodech (iteracích vnější smyčky). Pořadí zpracování hran je pevně dané — v každém průchodu se projde stejný seznam. Start je $A$.
b) Co k tomu budeme potřebovat?
- Tato lekce — vnější smyčka $n-1$ průchodů, předčasné ukončení, detekční průchod.
- [L2.3] Relaxace hrany — relaxační krok, vektory $l$ a $p$, ostrá nerovnost.
- [L2.3] T01 — proč pořadí hran rozhoduje o počtu průchodů.
c) Jak nad úlohou uvažovat?
Veď si tabulku $l$ a $p$ po průchodech. V každém průchodu projdi hrany přesně v daném pořadí a vždy počítej s čerstvými hodnotami — když se $l(v)$ zlepší uprostřed průchodu, další hrany už vidí novou hodnotu (tak může jeden průchod urazit i několik hran nejkratší cesty). Zapisuj jen hrany, které opravdu relaxovaly; hrany s $l(v) = \infty$ nic neudělají ($\infty + c$ nic nepodleze). Jakmile celý průchod nic nezmění, můžeš skončit — a na závěr přidej detekční průchod (tady musí vyjít „bez záporného cyklu“, pozor ale na rovnosti).
d) Úplné řešení (vlastní — banka úlohu neřeší)
$n = 5$, hlavní smyčka má tedy nejvýše $4$ průchody. Hrany v pořadí $(B,E)\,2,\ (D,B)\,1,\ (B,D)\,2,\ (A,B)\,{-1},\ (A,C)\,4,\ (D,C)\,5,\ (B,C)\,3,\ (E,D)\,{-3}$.
Průchod 1: $(B,E), (D,B), (B,D)$ nic — $l(B) = l(D) = \infty$. $(A,B)$: $l(B) := 0 + (-1) = -1$, $p(B) := A$. $(A,C)$: $l(C) := 0 + 4 = 4$, $p(C) := A$. $(D,C)$ nic. $(B,C)$: $4 > -1 + 3 = 2$ → $l(C) := 2$, $p(C) := B$ (čerstvá hodnota $l(B)$ z téhož průchodu!). $(E,D)$ nic.
Průchod 2: $(B,E)$: $l(E) := -1 + 2 = 1$, $p(E) := B$. $(D,B)$ nic. $(B,D)$: $l(D) := -1 + 2 = 1$, $p(D) := B$. $(A,B), (A,C)$ nic. $(D,C)$: $1 + 5 = 6 > 2$ nic. $(B,C)$: $2 = 2$ — rovnost nerelaxuje (ostrý test). $(E,D)$: $1 > 1 + (-3) = -2$ → $l(D) := -2$, $p(D) := E$.
Průchod 3: žádná hrana nerelaxuje → fixpoint, algoritmus lze ukončit (průchod 4 už není potřeba).
| po průchodu | $l(A)$ | $l(B)$ | $l(C)$ | $l(D)$ | $l(E)$ |
|---|---|---|---|---|---|
| init | $0$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 1 | $0$ | $-1$ | $2$ | $\infty$ | $\infty$ |
| 2 | $0$ | $-1$ | $2$ | $-2$ | $1$ |
| 3 (beze změny → stop) | $0$ | $-1$ | $2$ | $-2$ | $1$ |
Výsledek: $l = (0, -1, 2, -2, 1)$, $p = (-,\ A,\ B,\ E,\ B)$. Strom nejkratších cest (SPT): hrany $A \to B$, $B \to C$, $B \to E$, $E \to D$ — např. do $D$ vede $A \to B \to E \to D$ s délkou $-1 + 2 - 3 = -2$.
Detekční průchod: žádná hrana nerelaxuje → graf neobsahuje záporný cyklus dosažitelný z $A$. Stojí za pohled, jak těsné to je: na hranách $(B,E)$, $(E,D)$ a $(D,B)$ vyjdou rovnosti ($-1+2 = 1 = l(E)$, $1-3 = -2 = l(D)$, $-2+1 = -1 = l(B)$) — cyklus $B \to E \to D \to B$ má totiž délku $2 - 3 + 1 = 0$. Nulový cyklus není záporný a ostrý test ho správně nehlásí.
Poznámka k počtu průchodů: s tímto pořadím hran stačily 2 „pracovní“ průchody + 1 ověřovací; horní mez $n - 1 = 4$ by si vynutilo až nejhorší pořadí (srov. řetízek v [L2.3] T01).
Krokovaný běh řešení T01 (pozor, spoiler — nejdřív vyplň tabulku sám na papír):