L2.3 Kapitola K2 — Nejkratší cesty (Slot 2) · [MUST]

Relaxace hrany

Jedna nová věc Elementární algoritmický krok relaxace hrany: if l(w) > l(v) + c(v,w) then l(w) := l(v) + c(v,w); p(w) := v — jediný stavební kámen, ze kterého jsou poskládané všechny algoritmy na nejkratší cesty v této kapitole.

Prerekvizity: [L2.2] Bellmanův princip optimality + Bellmanova rovnice. Tam jsme skončili pozorováním, že Bellmanova rovnice je soustava rovnic svazující neznámé vzdálenosti — a slíbili si, že algoritmy budou různé strategie jejího řešení. Dnes si postavíme jejich společný elementární krok.

Od rovnice k výpočtu: pracovní odhady místo vzdáleností

Bellmanova rovnice $l(s,w) = \min_{v \ne w}\{\,l(s,v) + c(v,w)\,\}$ mluví o hotových vzdálenostech. Algoritmus je ale na začátku nezná — musí s něčím začít a postupně se k vzdálenostem propracovat.

Zkus sám: s jakými hodnotami $l(\cdot)$ může algoritmus poctivě začít, když o grafu zatím nic nespočítal?

Jediné, co víme zadarmo: do startu se dostanu prázdnou cestou ($l(s) = 0$) a o ostatních vrcholech nevím nic — žádnou cestu do nich jsem zatím neviděl, takže $l(v) = \infty$ pro $v \ne s$. Přesně tak začínají všechny algoritmy kapitoly (slide 16 i 29):

l(s) := 0;   l(v) := ∞  pro v ≠ s;

Hodnotám $l(v)$ se říká labels (značky): jsou to pracovní odhady vzdáleností, ne vzdálenosti samotné. Algoritmus je bude postupně snižovat, dokud se neusadí na správných hodnotách.

Vedle značky $l(v)$ si budeme držet ještě předchůdce $p(v)$ — odkud jsme do $v$ aktuálně nejlevněji přišli. K čemu je, uvidíš za chvíli.

Jeden krok: relaxace hrany

Teď ten klíčový nápad. Mám rozpracované značky a koukám na jedinou hranu $(v,w)$ s váhou $c(v,w)$.

Zkus sám: co mi hrana $(v,w)$ říká o značkách $l(v)$ a $l(w)$? Kdy a jak pomocí ní můžu odhad $l(w)$ zlepšit?

Když se do $v$ umím dostat za $l(v)$, pak prodloužením o hranu $(v,w)$ se do $w$ dostanu za $l(v) + c(v,w)$. Pokud je to méně než můj dosavadní odhad $l(w)$, našel jsem lepší příchod do $w$ — přepíšu značku a zapamatuji si, kudy to šlo: $p(w) := v$. Pokud to méně není, nedělám nic.

To je celé. Tenhle test-a-přepis je přesně člen $l(s,v) + c(v,w)$ z Bellmanovy rovnice, vyhodnocený pro jednu konkrétní hranu na aktuálních odhadech.

Relaxace hrany — edge relaxation (vnitřní krok ze slidů 16 a 29)
if l(w) > l(v) + c(v,w) then
    l(w) := l(v) + c(v,w);   p(w) := v;
end

Tento krok je doslova (znak po znaku) vnitřní smyčka Dijkstrova algoritmu (slide 16) i Bellman-Fordova algoritmu (slide 29). V literatuře se mu říká relax — hrana $(v,w)$ je „napjatá“ (porušuje nerovnost), relaxací ji „povolíme“.

Prohlédni si jednu relaxaci krok za krokem:

K čemu je vektor předchůdců $p$

Slidy 16 a 29 popisují výstup algoritmů shodně: vektory $l$ a $p$ — pro $v \in V(G)$ je $l(v)$ délka nejkratší cesty z $s$ a $p(v)$ předchozí vrchol na ní; pro $v$ nedosažitelný z $s$ je $l(v) = \infty$ a $p(v)$ nedefinované.

Zkus sám: vzdálenost $l(w)$ už mám — jak z hodnot $p(\cdot)$ zrekonstruuji samotnou nejkratší cestu do $w$?

Couváním: $p(w)$ říká, odkud nejkratší cesta do $w$ přišla; $p(p(w))$ odkud přišla tam; … a tak dál, dokud nedojdu do $s$. Posloupnost pak otočím: $s \to \dots \to p(p(w)) \to p(w) \to w$.

Každý vrchol si pamatuje jen jednoho předchůdce, takže hrany $\{(p(v), v)\}$ dohromady tvoří strom zakořeněný v $s$ — shortest paths tree, SPT (strom nejkratších cest). Jeden vektor $p$ tak kóduje nejkratší cesty do všech vrcholů najednou.

Co relaxace zaručuje (a co ne)

Zkus sám: může se značka $l(w)$ relaxacemi někdy „pokazit“ — tj. klesnout pod skutečnou vzdálenost $l(s,w)$?

Ne (v grafu bez záporných cyklů). Každá konečná hodnota $l(w)$ vznikla řetězem relaxací $s \to \dots \to w$, takže je to délka skutečného spojení z $s$ do $w$ v grafu. A žádné spojení nemůže být kratší než nejkratší cesta — případné cykly v něm mají váhu $\ge 0$, takže jejich vypuštění délku nezvýší.

Značky se tedy ke vzdálenostem blíží vždy shora: $l(w) \ge l(s,w)$ po celou dobu běhu a relaxace je jen snižují. Otázka je, kdy dolů „dopadnou“ — a na to odpovídá další pozorování.

Zkus sám: kdy už nemá smysl relaxovat? Co o značkách víš ve chvíli, kdy se žádnou relaxací nedají snížit?

„Žádná hrana se nedá relaxovat“ znamená, že pro každou hranu $(v,w)$ platí $l(w) \le l(v) + c(v,w)$. Spolu s předchozím pozorováním ($l$ nikdy nepodleze vzdálenosti a každá konečná značka je dosažitelná skutečným spojením) to znamená, že značky splňují Bellmanovu rovnici z [L2.2] — a jsou rovny vzdálenostem. Stav „nic nejde relaxovat“ je tedy cíl výpočtu: relaxace je lokální krok směrem ke splnění Bellmanovy rovnice.

(Tohle je zatím intuice — pořádné důkazy korektnosti Dijkstry a Bellman-Forda patří do kapitoly K3, tady v K2 nás zajímá běh a použití.)

Na pořadí relaxací záleží

Správné značky dostaneme, ať relaxujeme v jakémkoli pořadí — jen to může trvat různě dlouho. Sleduj na miniaturním řetízku:

Zkus sám: co z toho plyne pro návrh algoritmu? Čím se asi budou lišit algoritmy téhle kapitoly, když elementární krok mají všechny stejný?

Právě strategií pořadí relaxací:

  • Dijkstra [L2.4] volí pořadí chytře — vždy expanduje vrchol s nejmenší značkou (potřebuje k tomu nezáporné váhy),
  • Bellman-Ford [L2.12] nic nevymýšlí — relaxuje všechny hrany pořád dokola (zvládne i záporné váhy),
  • SP v DAG [L2.13] relaxuje hrany v topologickém pořadí — každou právě jednou,
  • Floyd-Warshall [L2.14] dělá týž porovnávací krok pro všechny dvojice vrcholů najednou.

Až je v dalších lekcích uvidíš, hledej v pseudokódu vždy stejné jádro — tenhle if.

Pozor: značka ≠ vzdálenost (dokud běh neskončí)
Key takeaways — L2.3
T01 Order of relaxations on a chain zdroj: prezentace/03_SPT_KO.md, slide 30 (příklad k Bellman-Fordovi — algoritmus sám probereme v [L2.12])
Assignment (EN, dle slidu 30)

Consider the chain of 4 nodes with edges $(1,2)$, $(2,3)$, $(3,4)$ of weights $-2$, $1$, $2$. Find the shortest paths tree from node $1$ by repeated passes in which every edge of the graph is relaxed. Assuming the edges to be processed (i) in the worst order, from right to left, and (ii) in the best order, from left to right — how many passes over all edges does each ordering require to obtain the shortest paths tree?

a) Co je v zadání?

Řetízek $1 \to 2 \to 3 \to 4$. Opakovaně projíždíme všechny tři hrany a relaxujeme; ptáme se, kolik průchodů je potřeba, když hrany v průchodu bereme zprava doleva (nejhorší pořadí), a kolik, když je bereme zleva doprava (nejlepší pořadí).

b) Co k tomu budeme potřebovat?

  • Tato lekce — relaxace hrany, inicializace $l(1)=0$, $l(v)=\infty$ jinak.
  • [L2.2] — proč se vzdálenosti smí skládat z mezivýsledků.

c) Jak nad úlohou uvažovat?

Veď si vektor $l = (l(1), l(2), l(3), l(4))$ a v každém průchodu poctivě otestuj všechny tři hrany v zadaném pořadí. Klíčové pozorování: relaxace $(v,w)$ něco udělá, jen když už $l(v)$ je konečné — informace se šíří od startu „po směru“ hran. Co se stane, když hrany testuju proti směru šíření?

d) Úplné řešení

(i) Nejhorší pořadí — zprava doleva: v každém průchodu testujeme $(3,4)$, $(2,3)$, $(1,2)$. Init $l = (0, \infty, \infty, \infty)$.

  • Průchod 1: $(3,4)$: $l(3)=\infty$, nic. $(2,3)$: $l(2)=\infty$, nic. $(1,2)$: $\infty \gt 0+(-2)$ → $l(2):=-2$, $p(2):=1$. Stav $l = (0, -2, \infty, \infty)$ — provedl se jen krok a).
  • Průchod 2: $(3,4)$: nic. $(2,3)$: $\infty \gt -2+1$ → $l(3):=-1$, $p(3):=2$. $(1,2)$: nic. Stav $l = (0, -2, -1, \infty)$ — krok b).
  • Průchod 3: $(3,4)$: $\infty \gt -1+2$ → $l(4):=1$, $p(4):=3$. Stav $l = (0, -2, -1, 1)$ — krok c). SPT hotov: 3 průchody.

(ii) Nejlepší pořadí — zleva doprava: $(1,2)$: $l(2):=-2$; hned poté $(2,3)$: $l(3):=-1$; hned poté $(3,4)$: $l(4):=1$. Kroky a), b), c) proběhnou všechny v 1 průchodu.

V obou případech vyjde týž výsledek $l = (0,-2,-1,1)$, $p = (-, 1, 2, 3)$ — pořadí nemění výsledek, jen počet průchodů. Informace teče od startu po hranách: pořadí „proti proudu“ posune frontu poznání o jediný vrchol za průchod. Přesně tahle úvaha za chvíli dá Bellman-Fordovi [L2.12] jeho hranici $n-1$ průchodů — a chytrá volba pořadí je celý trik Dijkstry [L2.4] a SP v DAG [L2.13].

Krokovaná verze řešení (pozor, spoiler — nejdřív si to zkus na papír):

T02 Relax until done & reconstruct the path from p zdroj: vlastní procvičovací úloha na koncept slidů 16/29 prezentace/03_SPT_KO.md (význam vektorů l a p)
Assignment (EN, procvičovací — koncept slidů 16 a 29)

Consider the digraph with nodes $s$, $a$, $b$, $c$ and edges $(s,a)$, $(s,b)$, $(a,b)$, $(a,c)$, $(b,c)$ with weights $1$, $4$, $2$, $5$, $1$. The vectors $l$ and $p$ currently hold $l(s)=0$, $l(a)=1$, $l(b)=4$, $l(c)=6$ and $p(a)=s$, $p(b)=s$, $p(c)=a$.

(i) Which edges can still be relaxed, i.e. satisfy $l(w) \gt l(v) + c(v,w)$? (ii) Perform relaxations until no edge can be relaxed and give the final vectors $l$ and $p$. (iii) Use the vector $p$ to reconstruct the shortest $s$–$c$ path.

a) Co je v zadání?

Rozpracovaný výpočet: značky $l$ a předchůdci $p$ uprostřed běhu. Máme (i) najít hrany, které ještě jdou relaxovat, (ii) dorelaxovat do stavu, kdy už nic nejde (= Bellmanova rovnice platí, značky jsou vzdálenosti), a (iii) z vektoru $p$ vyčíst nejkratší cestu do $c$.

b) Co k tomu budeme potřebovat?

  • Tato lekce — test relaxace, stav „nic nejde relaxovat“, rekonstrukce cesty couváním po $p$.

c) Jak nad úlohou uvažovat?

Projdi všech pět hran a u každé spočti $l(v) + c(v,w)$ vs. $l(w)$ — pozor, test je ostrý (rovnost nestačí). Po každé provedené relaxaci se situace mění, takže hrany, které dřív neprošly testem, otestuj znovu. U (iii) začni v $c$ a couvej.

d) Úplné řešení

(i) Test všech hran na stavu $l = (0, 1, 4, 6)$:

  • $(s,a)$: $1 \gt 0+1$? Ne (rovnost).
  • $(s,b)$: $4 \gt 0+4$? Ne (rovnost).
  • $(a,b)$: $4 \gt 1+2 = 3$? Ano — relaxovatelná.
  • $(a,c)$: $6 \gt 1+5 = 6$? Ne (rovnost — ostrý test nepustí).
  • $(b,c)$: $6 \gt 4+1 = 5$? Ano — relaxovatelná.

(ii) Relaxuj $(a,b)$: $l(b) := 3$, $p(b) := a$. Tím se změnil vstup hrany $(b,c)$ — otestuj znovu: $6 \gt 3+1 = 4$ → relaxuj: $l(c) := 4$, $p(c) := b$. Další kolo testů: $(s,a)$ rovnost, $(s,b)$: $3 \gt 4$? ne, $(a,b)$ rovnost, $(a,c)$: $4 \gt 6$? ne, $(b,c)$ rovnost — nic nejde relaxovat. Finální stav:

$$l = (l(s), l(a), l(b), l(c)) = (0,\, 1,\, 3,\, 4), \qquad p(a) = s,\; p(b) = a,\; p(c) = b.$$

(Kdybychom v (ii) začali hranou $(b,c)$, dostali bychom dočasně $l(c)=5$ — a po relaxaci $(a,b)$ by hrana $(b,c)$ prošla testem znovu: $5 \gt 3+1$. Výsledek je stejný, jen o krok později — pořadí mění průběh, ne výsledek, přesně jako v T01.)

(iii) Couvání z $c$: $p(c) = b$, $p(b) = a$, $p(a) = s$ → otočením dostaneme nejkratší cestu $s \to a \to b \to c$ s délkou $1 + 2 + 1 = 4 = l(c)$ ✓. Hrany $(s,a), (a,b), (b,c)$ jsou zároveň strom nejkratších cest (SPT) z $s$.

← Předchozí L2.2 · Bellmanův princip optimality + Bellmanova rovnice