Korektnost Bellman-Forda
Běh Bellman-Forda i mechaniku detekce záporného cyklu už umíš z [L2.12] Bellman-Fordův algoritmus + detekce záporného cyklu (běh) a nebudeme je vykládat znovu: relaxuj [L2.3] všechny hrany $(n-1)$-krát, žádné uzavírání. Dnes splatíme dluh, který tam zůstal viset jako „intuice“: PROČ stačí $n-1$ průchodů a proč relaxovatelná hrana v $n$-tém průchodu dokazuje záporný cyklus. Je to žebříček důkazů #4 a explicitní téma ústní zkoušky („Bellman-Ford + záporný cyklus“).
Jaký invariant zvolit
U Dijkstry [L3.2] jsme korektnost dokázali invariantem přes rostoucí množinu uzavřených vrcholů $R$: „kdo je v $R$, má značku správně“.
Zkus sám: Bellman-Ford žádnou množinu $R$ nemá — nic neuzavírá, všechny značky jsou dočasné až do konce. Přes co tedy povedeme indukci a jak by mohl znít invariant?
Jediné, co u Bellman-Forda monotónně roste, je počet dokončených průchodů (iterací vnější smyčky). Indukce tedy poběží přes počet iterací $k$ — stejná kostra „invariant přes něco rostoucího“ jako u Dijkstry, jen místo množiny $R$ čítač průchodů.
A invariant? V [L2.12] jsme si intuici už řekli: po $k$ průchodech jsou „zvládnuté“ nejkratší cesty s nejvýše $k$ hranami — každý průchod prodlouží zvládnutý úsek každé nejkratší cesty aspoň o jednu hranu. Dnes to zpřesníme na větu, která se dá poctivě dokázat.
Domluvme značení přesně podle slidu 31 (EN 1:1):
Let
- $l^k(w)$ is the $l(w)$ label after $k$ iterations of the external loop
- $P^k$ is the shortest $s$-$w$-path with at most $k$ edges and let $e = (v, w)$ be the last edge of this path
- $c(E(P^k))$ is the length of path $P^k$
Then $l^k(w) \le c(E(P^k))$.
Zkus sám: proč věta tvrdí jen nerovnost $\le$, a ne rovnost? (Vzpomeň na řetízek z úlohy [L2.3] T01 — co udělá šťastné pořadí hran v jediném průchodu?)
Protože značka může být „napřed“. Slide 31 to říká přímo (EN 1:1): „the $l^k(w) \le c(E(P^k))$ is inequality, since the $l^k(w)$ is the length of the path which might go over more than $k$ edges (see example with four nodes in the chain), but the $P^k$ path is defined to have at most $k$ edges.“
Konkrétně: v řetízku $1 \to 2 \to 3 \to 4$ s nejlepším pořadím hran (zleva doprava) doteče informace už v prvním průchodu až do vrcholu $4$ — značka $l^1(4)$ pak odpovídá cestě se třemi hranami, zatímco $P^1$ smí mít hranu jedinou (a tady ani neexistuje, takže $c(E(P^1)) = \infty$). Uvidíš to na stepperu níže.
(Poznámka navíc, slidy ji nechávají mlčky: pokud žádná $s$–$w$ cesta s $\le k$ hranami neexistuje, čteme $c(E(P^k)) = \infty$ a nerovnost platí triviálně.)
Důkaz věty indukcí přes $k$
Zkus sám: báze $k = 1$. Co víš o značce $l^1(w)$ po prvním průchodu — a co je vlastně $P^1$?
$P^1$ je nejkratší $s$–$w$ cesta s nejvýše jednou hranou, tedy samotná hrana $(s,w)$ (existuje-li). V prvním průchodu vnitřní smyčka otestuje každou hranu grafu, tedy i $(s,w)$ — a protože $l(s) = 0$ od inicializace (a bez záporného cyklu už se nezlepší), po testu platí $l^1(w) \le l(s) + c(s,w) = c(s,w)$. Slide 32: „For $k = 1$ it holds, because $l^1(w) \le c(s,w)$.“ Báze hotova.
Indukční krok. Nechť věta platí po $k-1$ iteracích a vezmi libovolný vrchol $w$ s cestou $P^k$; označ $e = (v,w)$ její poslední hranu. Rozlož si tvrzení na tři stavební kameny — každý si zkus nejdřív sám:
Zkus sám (kámen 1 — BPO): co víš o úseku cesty $P^k$ od $s$ do $v$? Kolik má hran a může existovat lepší?
Prefix $P^k[s,v]$ má nejvýše $k-1$ hran (poslední hranu $(v,w)$ jsme odřízli). A podle Bellmanova principu optimality [L2.2] je to nejkratší taková cesta: kdyby existovala kratší $s$–$v$ cesta s $\le k-1$ hranami, vyměníme ji za prefix a dostaneme kratší $s$–$w$ cestu s $\le k$ hranami — spor s optimalitou $P^k$. Prefix je tedy přesně cesta $P^{k-1}[s,v]$ ze značení věty a platí
$$c(E(P^{k-1}[s,v])) + c(v,w) = c(E(P^k)).$$Zkus sám (kámen 2 — IH): co o vrcholu $v$ říká indukční předpoklad?
Indukční předpoklad aplikovaný na $v$ (a jeho nejkratší cestu s $\le k-1$ hranami): po $k-1$ iteracích
$$l^{k-1}(v) \le c(E(P^{k-1}[s,v])).$$Zkus sám (kámen 3 — ALG): proč po $k$-té iteraci platí $l^k(w) \le l^{k-1}(v) + c(v,w)$? (Co přesně udělá vnitřní smyčka s hranou $(v,w)$ — a nevadí, že se $l(v)$ může během průchodu změnit?)
V $k$-té iteraci vnější smyčky projde vnitřní smyčka všechny hrany, tedy v nějakém okamžiku otestuje i $(v,w)$. V tom okamžiku je značka $v$ nejvýše $l^{k-1}(v)$ — značky nikdy nerostou [L2.3], jen klesají. Po testu (ať relaxace proběhla, nebo už platilo lepší) je $l(w) \le l(v) + c(v,w) \le l^{k-1}(v) + c(v,w)$ — a do konce průchodu může $l(w)$ už jen dál klesnout. Čerstvější (menší) hodnota $l(v)$ z téhož průchodu nerovnost jedině zesílí.
Složením tří kamenů vznikne řetízek ze slidu 32 (1:1):
$$l^k(w) \overset{ALG}{\le} l^{k-1}(v) + c(v,w) \overset{IH}{\le} c(E(P^{k-1}[s,v])) + c(v,w) \overset{BPO}{=} c(E(P^k)). \qquad \blacksquare$$Celý indukční krok si přehraj na schématu (podle obrázku slidu 32):
„While assuming $^{IH}$ that we had $l^k(v)$ better than or equal to the shortest $s$-$v$-path with at most $k - 1$ edges in iteration $k - 1$, in iteration $k$ of the algorithm $^{ALG}$ we will create $l^k(w)$ better than or equal to the shortest $s$-$w$-path with at most $k$ edges since the shortest path consists of the shortest paths $^{BPO}$.“
[Pozn.: slide má v indexu značky překlep — z indukčního předpokladu po iteraci $k-1$ má být $l^{k-1}(v)$, ne $l^k(v)$, jak jsme značku používali v řetízku výše.]
Z věty ke korektnosti: $k = n-1$
Věta dává jen horní odhad $\le$. Korektnost ale chce rovnost: po skončení má být $l(w)$ přesně délka nejkratší cesty.
Zkus sám: proč po $k = n-1$ iteracích platí i obrácená nerovnost $l^k(w) \ge c(E(P^k))$? (Dvě otázky: čím je hodnota $l(w)$ v každém okamžiku běhu? A co je $P^{n-1}$ zač?)
① Co je $P^{n-1}$: každá cesta v grafu s $n$ vrcholy má nejvýše $n-1$ hran [L2.2], takže omezení „nejvýše $n-1$ hran“ už nic neomezuje — $P^{n-1}$ je nejkratší $s$–$w$ cesta vůbec, $c(E(P^{n-1})) = \mathrm{dist}(w)$.
② Čím je $l(w)$: každá konečná značka vznikla řetězem relaxací, takže $l(w)$ je v každém okamžiku délka skutečného existujícího sledu $s \to \cdots \to w$ (rekonstruuješ ho couváním po vektoru $p$ [L2.3]). A protože graf nemá záporný cyklus, žádný sled není kratší než nejkratší cesta [L2.1]. Tedy $l^{n-1}(w) \ge \mathrm{dist}(w) = c(E(P^{n-1}))$.
Slide 33 totéž říká úsporně (EN 1:1): „because no path has more than $n - 1$ edges and no path is shorter than the shortest one.“
In iteration $k = n - 1$ we will obtain $l^k(w) = c(E(P^k))$
- because the above theorem implies $l^k(w) \le c(E(P^k))$
- and $l^k(w) \ge c(E(P^k))$ because no path has more than $n - 1$ edges and no path is shorter than the shortest one.
Zkus sám: u Dijkstry měla nezápornost hran v důkazu „dvě přesné adresy“ [L3.2]. Kde přesně v dnešním důkazu pracuje předpoklad „graf bez záporného cyklu“?
Také na dvou adresách:
- V BPO — výměnný argument Bellmanova principu potřebuje, aby šlo podcesty vyměňovat bez zacyklení do $-\infty$; přesně tam jsme předpoklad potřebovali už při jeho důkazu ([L2.2] T01, případ 2).
- V závěrečném $\ge$ — „žádný sled není kratší než nejkratší cesta“ [L2.1]. Se záporným cyklem by sled mohl obíhat a podlézt jakoukoli cestu; rovnost při $k = n-1$ by padla (a právě toho si všimne detekce níže).
Naopak nezápornost jednotlivých hran nikde potřeba není — proto Bellman-Ford záporné hrany zvládá, zatímco Dijkstra ne.
Invariant v akci: řetízek ze slidu 30
Propočítej si větu na nejmenší rozumné instanci — řetízku $1 \to 2 \to 3 \to 4$ s váhami $-2, 1, 2$ ze slidu 30 (znáš ho z [L2.3] T01). V každém framu porovnej značky $l^k$ s hodnotami $c(E(P^k))$:
Detekce záporného cyklu jako důsledek věty
Mechaniku detekce znáš z [L2.12]: po $n-1$ průchodech přidej $n$-tý kontrolní a pokud nějaká hrana ještě relaxuje, ohlaš záporný cyklus. Teď to umíme zdůvodnit — a to je přesně část, na kterou se ptá ústní.
Zkus sám: předpokládej, že graf záporný cyklus NEMÁ. Proč pak v $n$-tém průchodu nemůže relaxovat žádná hrana? (Použij právě dokázanou korektnost.)
Bez záporného cyklu je po $n-1$ průchodech $l(w) = \mathrm{dist}(w)$ pro všechny vrcholy (právě dokázáno). Skutečné nejkratší vzdálenosti ale splňují trojúhelníkovou nerovnost: pro každou hranu $(v,t)$ je
$$\mathrm{dist}(t) \le \mathrm{dist}(v) + c(v,t),$$protože nejkratší cesta do $v$ prodloužená o hranu $(v,t)$ je sled do $t$ — a žádný sled není pod $\mathrm{dist}(t)$ [L2.1]. Test $l(t) > l(v) + c(v,t)$ tedy nikde nevystřelí.
Kontrapozice: vystřelí-li test na nějaké hraně, korektnost neplatí — a jediný předpoklad, který jsme mohli porušit, je „graph without a negative cycle“. Graf tedy záporný cyklus obsahuje (dosažitelný z $s$). Slide 34 (1:1): „The Bellman-Ford algorithm can detect a negative cycle that is reachable from vertex $s$ while checking triangular inequality for resulting $l$.“ Pro cykly nedosažitelné z $s$ přidej $s'$ s hranami $c(s',v) = 0$ — proč to žádný nový cyklus nevytvoří, sis rozmyslel v [L2.12].
Tahle detekce není jen zkouškové cvičení: v kapitole K4 na ní stojí cycle canceling pro minimum cost flow [L4.11] — záporný cyklus v reziduálním grafu se hledá právě Bellman-Fordem (cvičení cv09).
Pozor: nebezpečné polopravdy u tohoto důkazu- „Věta o $k$-té iteraci dává rovnost.“ NE — jen $\le$. Při šťastném pořadí hran je značka „napřed“ (odpovídá cestě s více než $k$ hranami) a nerovnost je ostrá; rovnost nastává až při $k = n-1$, a to díky druhé, samostatně dokazované nerovnosti $\ge$.
- „$P^k$ je cesta s přesně $k$ hranami.“ NE — s nejvýše $k$ hranami. S „přesně“ by indukční krok nefungoval (nejkratší cesta do $w$ může mít hran méně) a $c(E(P^k))$ by ani nemuselo klesat s $k$.
- „Bellman-Ford potřebuje nezáporné hrany jako Dijkstra.“ NE — důkaz nezápornost hran nikde nepoužil; potřebuje jen absenci záporného cyklu, a to na dvou přesných adresách: BPO [L2.2] a „sled $\ge$ nejkratší cesta“ [L2.1].
- „Hrana, na které detekce vystřelí, leží na záporném cyklu.“ NE — kontrapozice dokazuje jen existenci cyklu, nelokalizuje ho [L2.12].
Key takeaways — L3.7- Věta o $k$-té iteraci: $l^k(w) \le c(E(P^k))$, kde $P^k$ je nejkratší $s$–$w$ cesta s nejvýše $k$ hranami. Důkaz indukcí přes $k$; řetízek $l^k(w) \overset{ALG}{\le} l^{k-1}(v) + c(v,w) \overset{IH}{\le} c(E(P^{k-1}[s,v])) + c(v,w) \overset{BPO}{=} c(E(P^k))$.
- Korektnost: při $k = n-1$ rovnost — $\le$ z věty, $\ge$ protože žádná cesta nemá víc než $n-1$ hran a $l(w)$ je vždy délka skutečného sledu, který bez záporného cyklu nepodleze nejkratší cestu [L2.1].
- Detekce záporného cyklu: korektní $l$ splňuje trojúhelníkovou nerovnost na každé hraně → $n$-tý průchod mlčí; relaxovatelná hrana v $n$-tém průchodu = kontrapozicí záporný cyklus (dosažitelný z $s$; jinak $s'$-trik) [L2.12].
- Předpoklad „bez záporného cyklu“ má dvě přesné adresy: BPO a závěrečné $\ge$; nezápornost hran není potřeba nikde. Stejná indukční kostra jako u Dijkstry [L3.2] — invariant přes počet iterací místo množiny $R$.
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(a) Prove the correctness of the algorithm, i.e., that after $n-1$ iterations of the external loop $l(w)$ equals the length of the shortest $s$-$w$-path for every $w \in V(G)$. (b) Explain how the algorithm can be extended to detect a negative cycle and prove that the detection is correct.
a) Co je v zadání?
Čistě důkazová úloha (formát ústní zkoušky): je dán pseudokód Bellman-Forda — tentýž, který umíš oditerovat z [L2.12] — a chce se důkaz korektnosti plus zdůvodnění detekce záporného cyklu. Žádný konkrétní graf; odevzdává se text důkazu.
b) Co k tomu budeme potřebovat?
- Tato lekce — věta o $k$-té iteraci, řetízek ALG/IH/BPO, krok $k = n-1$, kontrapozice detekce.
- [L2.12] Bellman-Ford (běh) — vnější/vnitřní smyčka, $n$-tý kontrolní průchod, $s'$-trik.
- [L2.2] Bellmanův princip optimality — výměnný argument pro BPO krok.
- [L2.1] Záporné váhy ano, záporné cykly ne — „žádný sled není kratší než nejkratší cesta“.
c) Jak nad úlohou uvažovat?
Začni strukturou, ne nerovnostmi: ① zaveď značení $l^k(w)$, $P^k$, $c(E(P^k))$; ② vyslov větu o $k$-té iteraci (pozor: nejvýše $k$ hran a jen $\le$); ③ indukce — báze $k=1$, krok = řetízek tří kroků, každý se svým zdůvodněním (ALG = hrana $(v,w)$ se v $k$-tém průchodu testuje a značky nerostou; IH = předpoklad pro $v$; BPO = prefix je optimální); ④ při $k=n-1$ doplň obrácenou nerovnost; ⑤ detekce kontrapozicí přes trojúhelníkovou nerovnost. U tabule se nejčastěji ptají: proč je ve větě nerovnost a kde se použil zákaz záporného cyklu.
d) Úplné řešení (dle slidů 31–34)
(a) Značení. $l^k(w)$ = značka $l(w)$ po $k$ iteracích vnější smyčky; $P^k$ = nejkratší $s$–$w$ cesta s nejvýše $k$ hranami, $e = (v,w)$ její poslední hrana; $c(E(P^k))$ = délka $P^k$.
Věta ($k$-tá iterace). $l^k(w) \le c(E(P^k))$. (Jen nerovnost: $l^k(w)$ může být délka cesty s více než $k$ hranami, došla-li informace při šťastném pořadí hran dál; $P^k$ má z definice nejvýše $k$ hran.)
Důkaz indukcí přes $k$.
- Báze $k=1$: v prvním průchodu se testuje i hrana $(s,w)$ při $l(s)=0$, takže $l^1(w) \le c(s,w) = c(E(P^1))$.
- Indukční předpoklad (IH): po $k-1$ iteracích $l^{k-1}(v) \le c(E(P^{k-1}[s,v]))$.
- Algoritmus (ALG): v $k$-té iteraci vnitřní smyčka otestuje hranu $(v,w)$; značky nikdy nerostou, takže po $k$-té iteraci $l^k(w) \le l^{k-1}(v) + c(v,w)$.
- Bellmanův princip (BPO): prefix $P^k[s,v]$ má nejvýše $k-1$ hran a je nejkratší takový (jinak výměnou zkrátíme $P^k$ — spor), tedy $c(E(P^{k-1}[s,v])) + c(v,w) = c(E(P^k))$.
Složením:
$$l^k(w) \overset{ALG}{\le} l^{k-1}(v) + c(v,w) \overset{IH}{\le} c(E(P^{k-1}[s,v])) + c(v,w) \overset{BPO}{=} c(E(P^k)).$$Korektnost. V iteraci $k = n-1$ platí $l^k(w) = c(E(P^k))$:
- $l^k(w) \le c(E(P^k))$ z věty;
- $l^k(w) \ge c(E(P^k))$, protože žádná cesta nemá víc než $n-1$ hran (takže $P^{n-1}$ je nejkratší $s$–$w$ cesta vůbec) a žádná cesta není kratší než nejkratší — $l(w)$ je vždy délka skutečného sledu vzniklého relaxacemi a bez záporného cyklu žádný sled nejkratší cestu nepodleze.
Po $n-1$ iteracích je tedy $l(w) = \mathrm{dist}(w)$ pro všechny vrcholy ($\infty$ pro nedosažitelné — konečnou značku nemá z čeho vzniknout relaxace). $\blacksquare$
(b) Detekce záporného cyklu. Po hlavní smyčce přidej $n$-tý kontrolní průchod (slide 34, 1:1):
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
endKorektnost detekce: nemá-li graf záporný cyklus, je po $n-1$ průchodech $l = \mathrm{dist}$ (část (a)) a skutečné vzdálenosti splňují trojúhelníkovou nerovnost $\mathrm{dist}(t) \le \mathrm{dist}(v) + c(v,t)$ pro každou hranu (nejkratší cesta do $v$ + hrana $(v,t)$ je sled do $t$) — test tedy nikde nevystřelí. Kontrapozicí: vystřelí-li test, předpoklad „bez záporného cyklu“ neplatí — graf obsahuje záporný cyklus dosažitelný z $s$. Cykly nedosažitelné z $s$: přidej vrchol $s'$ a hrany $c(s',v) = 0$ do všech vrcholů — do $s'$ žádná hrana nevede, takže žádný nový cyklus nevznikne, a z $s'$ je dosažitelný celý graf [L2.12].
Krátká zkoušková odpověď (kostra, kterou rozepíšeš): ① značení $l^k$, $P^k$ (nejvýše $k$ hran!); ② věta $l^k(w) \le c(E(P^k))$; ③ indukce: báze $l^1(w) \le c(s,w)$, krok $l^k(w) \overset{ALG}{\le} l^{k-1}(v)+c(v,w) \overset{IH}{\le} c(E(P^{k-1}[s,v]))+c(v,w) \overset{BPO}{=} c(E(P^k))$; ④ $k=n-1$: rovnost ($\le$ věta; $\ge$ sled vs. cesta + každá cesta $\le n-1$ hran); ⑤ detekce: korektní $l$ ⇒ trojúhelníková nerovnost ⇒ $n$-tý průchod mlčí; relaxace v $n$-tém průchodu ⇒ kontrapozicí záporný cyklus; $s'$-trik pro nedosažitelné. Zákaz záporného cyklu výslovně vyznač v BPO a v kroku ④.
This example illustrates iterations of the Bellman-Ford algorithm finding shortest paths tree from node 1. (Chain of four nodes $1 \to 2 \to 3 \to 4$ with edge weights $-2$, $1$, $2$; initial labels $[0, \infty, \infty, \infty]$.)
Assuming the edges to be processed in the internal loop:
- in the worst order, from right to left when only step a) is executed in the first iteration of the external loop, it requires 3 iterations of the external loop to obtain SPT
- in the best order, from left to right when steps a) b) c) are executed in the first iteration of the external loop, it requires only 1 iteration of the external loop to obtain SPT
Study questions (own): (i) For the worst order, write the vector $l^k$ after each iteration $k = 1, 2, 3$ together with $c(E(P^k))$ for every node, and verify the theorem $l^k(w) \le c(E(P^k))$. (ii) For the best order, find a node and an iteration where the inequality is strict. (iii) Run the $n$-th (checking) pass — what does it report and why?
a) Co je v zadání?
Miniinstance ze slidu 30: řetízek $1 \to 2 \to 3 \to 4$, váhy $-2, 1, 2$, start ve vrcholu 1. Úkol není jen oditerovat běh (to umíš z [L2.12] a [L2.3] T01) — máš u toho sledovat invariant: po každém průchodu porovnat značky s délkami nejkratších cest omezených počtem hran.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice $P^k$ a $c(E(P^k))$, věta o $k$-té iteraci, detekce.
- [L2.3] T01 — tentýž řetízek, počet průchodů podle pořadí hran.
c) Jak nad úlohou uvažovat?
Pro každý vrchol $w$ a každé $k$ si zvlášť polož dvě otázky: „co říká algoritmus“ ($l^k(w)$ — odsimuluj průchod v daném pořadí hran, s čerstvými hodnotami) a „co říká definice“ ($c(E(P^k))$ — existuje vůbec $s$–$w$ cesta s nejvýše $k$ hranami? V řetízku je to snadné: do vrcholu $j$ vede jediná cesta a má $j-1$ hran). Ostrou nerovnost hledej tam, kde značka „předběhla“ definici.
d) Úplné řešení (vlastní)
(i) Nejhorší pořadí — hrany zpracovávané zprava doleva: $(3,4), (2,3), (1,2)$ v každém průchodu. Do vrcholu $j$ vede jediná cesta $1 \to \cdots \to j$ s $j-1$ hranami, takže $c(E(P^k))$ je její délka pro $k \ge j-1$ a $\infty$ jinak:
| po iteraci $k$ | $l^k(2)$ | $c(E(P^k))$ pro 2 | $l^k(3)$ | $c(E(P^k))$ pro 3 | $l^k(4)$ | $c(E(P^k))$ pro 4 |
|---|---|---|---|---|---|---|
| $k=1$ | $-2$ | $-2$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| $k=2$ | $-2$ | $-2$ | $-1$ | $-1$ | $\infty$ | $\infty$ |
| $k=3$ | $-2$ | $-2$ | $-1$ | $-1$ | $1$ | $1$ |
(Průchod 1: $(3,4)$ i $(2,3)$ nic — $l = \infty$; $(1,2)$: $l(2) := -2$. Průchod 2: $(3,4)$ nic, $(2,3)$: $l(3) := -2+1 = -1$, $(1,2)$ nic. Průchod 3: $(3,4)$: $l(4) := -1+2 = 1$.) Věta platí všude — dokonce s rovností: nejhorší pořadí posune „frontu poznání“ přesně o jednu hranu za průchod, značky jsou přesně na hraně toho, co věta zaručuje. Potřeba $n-1 = 3$ iterací.
(ii) Nejlepší pořadí — hrany $(1,2), (2,3), (3,4)$: už v prvním průchodu proběhnou kroky a) b) c) s čerstvými hodnotami a $l^1 = [0, -2, -1, 1]$. Ale $c(E(P^1))$ je $-2$ pro vrchol 2 a $\infty$ pro vrcholy 3 a 4 (žádná cesta s $\le 1$ hranou tam nevede). Tedy např. pro vrchol 3:
$$l^1(3) = -1 < \infty = c(E(P^1)) \quad \text{— ostrá nerovnost (a pro vrchol 4 stejně: } 1 < \infty\text{).}$$Přesně případ z poznámky slidu 31: značka odpovídá cestě s více než $k$ hranami. SPT je hotové po 1 iteraci; druhý průchod nic nezmění (fixpoint → předčasné ukončení [L2.12]).
(iii) Kontrolní ($n$-tý) průchod: žádná hrana nerelaxuje — $l = (0, -2, -1, 1)$ splňuje na všech třech hranách trojúhelníkovou nerovnost s rovností ($-2 = 0 + (-2)$, $-1 = -2 + 1$, $1 = -1 + 2$; rovnost ostrý test nehlásí). Hlášení „bez záporného cyklu“ je správně: řetízek je DAG, žádný cyklus v něm není.