Škálování vah a zachování nejkratší cesty
Celou kapitolu řešíme, jak algoritmy snášejí záporné váhy: pro Dijkstru jsou zakázané území [L2.4], Bellman-Ford je zvládne, ale za cenu $\mathcal{O}(nm)$ [L2.12]. Na písemce se proto pravidelně objevuje lákavá myšlenka: „Tak ty záporné váhy prostě odstraníme — ke všem přičteme dostatečně velké $h$ a pustíme Dijkstru.“ Přesně tohle zkoumá dochovaná zkoušková podotázka (úloha T01 níže). Tahle lekce je o tom, kdy úprava vah nejkratší cestu zachová a kdy ji potichu rozbije.
Posun všech vah o $+h$
Zkus sám: ke všem vahám přičteš $h \ge |\min_{e} c(e)|$ — váhy jsou rázem nezáporné a Dijkstra smí běžet. Dostaneš ale nejkratší cestu původního grafu? Rozepiš si, co se stane s cenou jedné konkrétní cesty.
Cesta $P$ je posloupnost hran [L0.1] a její cena je součet vah. Po posunu:
$$c'(P) = \sum_{e \in P} \big(c(e) + h\big) = c(P) + h \cdot |P|,$$kde $|P|$ je počet hran cesty. Každá cesta tedy nedostane stejný příplatek — dostane $h$ za každou svou hranu. Cesta o třech hranách zdraží o $3h$, přímá hrana jen o $h$. Pořadí cest podle ceny se proto může přehodit: posun systematicky znevýhodňuje cesty s více hranami. Nejkratší cesta se obecně NEzachová.
Konkrétní protipříklad (silně souvislý, se zápornými vahami — přesně ve formátu, jaký chce zkouška): minimum vah je $-3$, vezmi tedy $h = 3$.
Zkus sám: spočítej obě $s \to t$ cesty v $G$ i v $G'$. Která vyhraje kde?
V $G$: cesta $s \to a \to t$ stojí $-2 + (-2) = -4$, přímá hrana $s \to t$ stojí $-3$. Vyhrává $s \to a \to t$ ($-4 < -3$).
V $G'$ (vše $+3$): cesta $s \to a \to t$ stojí $1 + 1 = 2$, přímá hrana $0$. Vyhrává $s \to t$ ($0 < 2$). Sedí to s formulkou: dvouhranná cesta zdražila o $2h = 6$ (z $-4$ na $2$), jednohranná jen o $h = 3$ (z $-3$ na $0$).
Nejkratší cesta v $G'$ tedy neodpovídá nejkratší cestě v $G$ — „vylepšený“ graf vrátí špatnou odpověď na původní otázku.
Zkus sám: najdi chybu. Dochovaná zkoušková odpověď tvrdila opak — „SPT computation is decided by the weight difference between pairs of edges: $c(e_i) - c(e_j) = d$; after adding $h$ we get $c(e_i) + h - (c(e_j) + h) = d$, the same difference — therefore SPT of $G$ corresponds to SPT of $G'$.“ Kde je díra v argumentu?
O nejkratší cestě nerozhodují rozdíly dvojic hran, ale součty vah podél celých cest — a porovnávané cesty mohou mít různý počet hran. V rozdílu cen dvou cest se $h$ nezkrátí jednou, přibyde $|P_1|$-krát na jedné a $|P_2|$-krát na druhé straně:
$$c'(P_1) - c'(P_2) = c(P_1) - c(P_2) + h\,\big(|P_1| - |P_2|\big).$$Zkrátí se jen pro $|P_1| = |P_2|$. V protipříkladu výše: $|P_1| - |P_2| = 2 - 1 = 1$, takže rozdíl cen se posunul o $h = 3$ — z $-4 - (-3) = -1$ na $2 - 0 = 2$, a vítěz se přehodil. (Zkoušející si chybu odpovědi pohlídal — na okraji je červeně připsáno „What about negative cycles?“ a opravná skica trojúhelníkového protipříkladu.)
- Všechny porovnávané cesty mají stejný počet hran. Pak je příplatek $h \cdot |P|$ všude stejný a pořadí se nemění. Příklad z TSP ([L3.8a] Metrický TSP): všechny hamiltonovské kružnice na $n$ vrcholech mají přesně $n$ hran — slide TSP doslova říká, že přičtením konstanty $h$ ke každé hraně se kritérium zvedne o $n \cdot h$ (a instance se stane metrickou).
- Posun „po vrcholech“ (potenciály). Johnsonův algoritmus (zmíněný u Floyda [L2.14]) přeznačkuje $c'(u,v) = c(u,v) + h(u) - h(v)$ s vhodnou funkcí $h$ na vrcholech: podél každé $s \to t$ cesty se vnitřní členy teleskopicky vyruší a cena vzroste o stejných $h(s) - h(t)$ — nezávisle na počtu hran. To je korektní cesta, jak se zbavit záporných vah; paušální $+h$ na hranu korektní není.
Násobení všech vah konstantou $k > 0$
Zkus sám: a co když všechny váhy vynásobíme $k > 0$? Rozepiš cenu cesty stejně jako u posunu.
$$c'(P) = \sum_{e \in P} k \cdot c(e) = k \cdot c(P).$$
Cena každé cesty se násobí stejným faktorem — žádný člen závislý na počtu hran. Pro $k > 0$ tedy platí $c(P_1) < c(P_2) \iff k\,c(P_1) < k\,c(P_2)$: pořadí cest se zachová, nejkratší cesta zůstane nejkratší a její délka se vynásobí $k$ (tj. $\min_P k\,c(P) = k \min_P c(P)$).
Zkus sám: ladí to s Bellmanovou rovnicí [L2.2]?
Ano. Když vzdálenosti $l(s,\cdot)$ splňují $l(s,w) = \min_v \{ l(s,v) + c(v,w) \}$, vynásob obě strany $k > 0$: protože kladná konstanta se protáhne přes minimum, dostaneš $k\,l(s,w) = \min_v \{ k\,l(s,v) + k\,c(v,w) \}$ — funkce $k \cdot l$ splňuje Bellmanovu rovnici grafu s vahami $k \cdot c$. Stejný argument „monotónní transformace zachová argmin“ jsme už použili u $-\log$ převodu [L2.7] (tam jsme díky němu směli ignorovat základ logaritmu — změna základu je právě přenásobení všech vah kladnou konstantou).
Bonus: i definovanost úlohy se zachová — cyklus má po vynásobení $k > 0$ stejné znaménko, takže záporné cykly nevzniknou ani nezmizí [L2.1]. Posun $+h$ naopak záporné cykly „vyléčí“ — což je samo o sobě podezřelé: v $G$ se záporným cyklem nejkratší cesta ani nemusí být rozumně definovaná, v $G'$ už ano, takže si nemohou odpovídat.
Zkus sám: co pokazí $k = -1$? A $k = 0$?
$k = -1$ otočí všechny nerovnosti: minimum se stane maximem. To není vada, ale trik — přesně takhle jsme hledali nejdelší cesty Floydem [L2.14] i v DAGu [L2.13]. „Zachování nejkratší cesty“ ale neplatí: nejkratší cesta v $-c$ je nejdelší v $c$.
$k = 0$ vše zploští na nulu — každá cesta je „nejkratší“, informace je pryč. Proto formulace v takeaways vždy zní $k > 0$.
Pozor: nebezpečná polopravda- „Záporné váhy posunu o $+h$ do nezáporna a pustím Dijkstru.“ NE — posun přidá $h \cdot |P|$, cesty s více hranami zdraží víc a vítěz se může přehodit (protipříklad výše). Korektní řešení záporných vah: Bellman-Ford [L2.12], v DAGu topologický průchod [L2.13], all-pairs Floyd [L2.14].
- Jediné bezpečné plošné škálování je násobení $k > 0$. A pozor na tichý předpoklad: úvaha porovnává ceny cest — nejlevnější cesta nemusí mít nejméně hran; o vztahu Dijkstry a počtu hran je hned další lekce [L2.16] Dijkstra a počet hran cesty.
Key takeaways — L2.15- Posun všech vah o $+h$ NEzachová nejkratší cestu: $c'(P) = c(P) + h \cdot |P|$ — cena roste úměrně počtu hran cesty, delší cesta dostane víc $+h$. Protipříklad: dvě $s \to t$ cesty s různým počtem hran (zde $-4$ vs. $-3$ → po $+3$: $2$ vs. $0$).
- Násobení všech vah $k$, $k > 0$, zachová nejkratší cestu: $c'(P) = k \cdot c(P)$ — každá cesta se škáluje stejně, argmin se nemění a délka nejkratší cesty se násobí $k$. Záporné cykly nevzniknou ani nezmizí.
- $k = -1$ prohodí min/max (trik na nejdelší cesty [L2.14]), $k \le 0$ tedy nejkratší cestu nezachovává.
- Posun $+h$ je v pořádku jen výjimečně: když všechny porovnávané cesty mají stejný počet hran (TSP kružnice — kapitola K3), nebo jako teleskopický posun přes potenciály vrcholů (Johnson).
- Toto je typická zkoušková podotázka „dokaž, nebo vyvrať protipříkladem“ — důkaz = rozpis $c'(P)$, protipříklad = malý graf se dvěma cestami různé délky (v počtu hran).
Consider having a strongly connected graph $G$, with a set of edges $E$, and with arbitrary edge weights from $\mathbb{Z}$; $c(e)$ denotes the weight of edge $e$.
3. Consider an integer $h$, $h \geq |\min_{e \in E} c(e)|$. Consider graph $G'$, which is identical to $G$, but every edge weight is increased by $h$. Does the shortest path between any two vertices in $G'$ correspond to the shortest path between the same vertices in $G$? If yes, explain why; if no, give a counterexample of graphs $G$ and $G'$.
a) Co je v zadání?
Silně souvislý graf s celočíselnými (i zápornými) vahami. Zvolí se celé $h$ aspoň tak velké jako absolutní hodnota nejmenší váhy — tedy přesně tolik, aby v $G'$ byly všechny váhy nezáporné. Otázka: odpovídají nejkratší cesty v $G'$ nejkratším cestám v $G$? Formát odpovědi je předepsaný: ano + vysvětlení, nebo ne + protipříklad (konkrétní dvojice $G$, $G'$).
b) Co k tomu budeme potřebovat?
- Tato lekce — rozpis $c'(P) = c(P) + h \cdot |P|$ a hotový protipříklad.
- [L0.1] Co je graf — cesta a její cena jako součet vah hran.
- [L2.1] Záporné váhy ano, záporné cykly ne — kontrola, že protipříklad má nejkratší cesty definované.
c) Jak nad úlohou uvažovat?
Volba $h \ge |\min c(e)|$ prozrazuje motivaci: udělat váhy nezáporné kvůli Dijkstrovi. Neptej se „změní se délky?“ (ty se změní vždy), ale „změní se vítěz?“ — rozepiš cenu cesty po posunu a všimni si členu závislého na počtu hran. Jakmile ho vidíš, protipříklad se staví sám: dvě konkurenční cesty, jedna krátká v hranách a jedna dlouhá, s cenami tak těsnými, aby je příplatek přehodil. Nezapomeň na požadavky zadání: graf má být silně souvislý (přidej zpáteční hranu) a bez záporného cyklu, ať jsou nejkratší cesty v $G$ definované. Pozor: dochovaná studentská odpověď (psala „yes“ s argumentem přes rozdíly dvojic hran) je chybná — viz try-otázka „najdi chybu“ v lekci.
d) Úplné řešení (vlastní)
Odpověď: NE, nejkratší cesty si obecně neodpovídají.
Důvod. Pro každou cestu $P$ platí $c'(P) = c(P) + h \cdot |P|$, kde $|P|$ je počet hran. Příplatek není konstantní — závisí na počtu hran, takže porovnání dvou cest s $|P_1| \ne |P_2|$ se může přehodit: $c'(P_1) - c'(P_2) = c(P_1) - c(P_2) + h(|P_1| - |P_2|)$.
Protipříklad. $G$ = graf z lekce: vrcholy $\{s, a, t\}$, hrany $c(s,a) = -2$, $c(a,t) = -2$, $c(s,t) = -3$, $c(t,s) = 10$ (zpáteční hrana zajišťuje silnou souvislost; všechny cykly jsou kladné: $s{\to}a{\to}t{\to}s = 6$, $s{\to}t{\to}s = 7$, takže nejkratší cesty v $G$ jsou definované [L2.1]). Minimum vah je $-3$, zvol $h = 3 \ge |-3|$; v $G'$ pak $c'(s,a) = c'(a,t) = 1$, $c'(s,t) = 0$, $c'(t,s) = 13$.
- V $G$: $c(s{\to}a{\to}t) = -4 \;<\; c(s{\to}t) = -3$ → nejkratší $s \to t$ cesta je $s \to a \to t$.
- V $G'$: $c'(s{\to}a{\to}t) = 2 \;>\; c'(s{\to}t) = 0$ → nejkratší je přímá hrana $s \to t$.
Nejkratší cesta v $G'$ tedy neodpovídá nejkratší cestě v $G$. $\blacksquare$
Poznámka navíc (stojí za zmínku u ústní): kdyby $G$ obsahoval záporný cyklus, je otázka rozbitá ještě dřív — v $G$ pak nejkratší cesta není rozumně definovaná (resp. její hledání je NP-těžké), zatímco v $G'$ s nezápornými vahami definovaná je; ani pak si „odpovídat“ nemohou. Přesně na to mířila červená poznámka zkoušejícího „What about negative cycles?“ u dochované (chybné) odpovědi „yes“.
5 výroků a říct zda platí nebo ne. Pokud platí, dokázat, pokud ne, udělat protipříklad. Výroky typu „když zvýšíme cenu hrany v grafu o násobek $k$, délka nejkratší cesty se také zvýší $k$-krát“ […]
a) Co je v zadání?
Formát „dokaž, nebo vyvrať protipříkladem“. Přepis výroku je bohužel dvojznačný: (i) všechny ceny hran se vynásobí $k$ („cenu hran v grafu“), nebo (ii) vynásobí se cena jedné hrany. Na písemce rozhodne přesné EN znění — zde vyřešíme obě čtení (a u obou předpokládáme, že nejkratší cesta je definovaná, tj. bez záporných cyklů).
b) Co k tomu budeme potřebovat?
- Tato lekce — $c'(P) = k \cdot c(P)$ a chování pro $k \le 0$.
- [L2.2] Bellmanův princip + rovnice — škálování vzdáleností $k \cdot l$.
c) Jak nad úlohou uvažovat?
U čtení (i) rozepiš cenu libovolné cesty po vynásobení — chybí tam jakýkoliv člen závislý na počtu hran (srovnej s posunem $+h$!), zbývá ošetřit znaménko $k$. U čtení (ii) hledej nejlacinější možný protipříklad: stačí, aby zdražená hrana na nejkratší cestě vůbec neležela?
d) Úplné řešení (vlastní)
Čtení (i): všechny váhy ×$k$, $k > 0$ — výrok PLATÍ. Důkaz: množina cest $s \to t$ se nemění a pro každou platí $c'(P) = k \cdot c(P)$. Pro $k > 0$ kladná konstanta projde přes minimum: $\min_P c'(P) = k \cdot \min_P c(P)$ — délka nejkratší cesty se zvýší přesně $k$-krát a optimum se realizuje toutéž cestou (argmin se zachová). $\blacksquare$
Doplnit meze platnosti se na „5 výroků“ vyplácí: pro $k = 0$ jsou všechny cesty nulové, pro $k < 0$ se min a max prohodí (trik ×$(-1)$ na nejdelší cesty [L2.14]) — tam výrok neplatí. A drobnost: „zvýší se $k$-krát“ u záporné délky znamená vynásobí se $k$ (např. $-4 \mapsto -8$ pro $k=2$) — číselně se tedy „sníží“; matematicky je výrok o $\min_P k\,c(P) = k \min_P c(P)$ v pořádku.
Čtení (ii): jen jedna hrana ×$k$ — výrok NEPLATÍ. Protipříklad: graf z lekce ($c(s,a) = c(a,t) = -2$, $c(s,t) = -3$, $c(t,s) = 10$), nejkratší $s \to t$ cesta je $s \to a \to t$ s délkou $-4$. Vynásob $k = 2$ pouze hranu $(t,s)$: $10 \mapsto 20$. Hrana na žádné $s \to t$ cestě neleží, takže nejkratší cesta i její délka $-4$ zůstávají — délka se nezvýšila $k$-krát. (A i hrana na nejkratší cestě výrok vyvrací: ×$2$ na hraně $(s,a)$ dá cestu $-4-2=-6 \ne 2 \cdot (-4) = -8$, protože se škáluje jen jeden sčítanec.)