Dijkstra a počet hran cesty
Minulá lekce [L2.15] Škálování vah skončila varováním: posun vah o $+h$ rozbíjí nejkratší cestu, protože do ceny přimíchá člen $h \cdot |P|$ závislý na počtu hran. Dnes se na ten tichý předpoklad podíváme zpříma. Slovo „nejkratší“ (shortest path, nejkratší cesta) totiž v běžné řeči svádí k představě „nejméně kroků“ — a přesně na tuhle záměnu míří dochovaný zkouškový výrok „Dijkstrův algoritmus nalezne vždy nejkratší cestu s nejmenším počtem hran“ (úloha T01 níže).
Co Dijkstra vlastně minimalizuje
Zkus sám: projdi si v hlavě pseudokód Dijkstry [L2.4]. Na kterém řádku do výpočtu vstupuje počet hran cesty?
Na žádném. Jediné porovnání v celém algoritmu je relaxační test [L2.3]: if l(w) > l(v) + c(v, w) — a výběr vrcholu s nejmenší značkou $l$. Obojí pracuje výhradně se součty vah. Kolik hran cesta má, ovlivní nanejvýš to, kolikrát se po cestě sčítalo; jako kritérium se počet hran nikde netestuje, nepenalizuje ani neeviduje. Definice úlohy je stejná [L2.1]: nejkratší cesta = cesta s nejmenším součtem vah, o počtu hran neříká nic.
Zkus sám: navrhni co nejmenší graf s nezápornými vahami, ve kterém má nejlevnější $s \to t$ cesta víc hran než nějaká jiná $s \to t$ cesta.
Stačí dvě konkurenční cesty: jedna „dlouhá v hranách, ale levná“, druhá „krátká v hranách, ale drahá“. Třeba řetízek tří hran po $1$ (cena $3$) proti přímé hraně s vahou $10$:
Pusť si běh — Dijkstra se ani na okamžik nezaváhá nad tím, že přímá hrana je „jen jeden krok“:
Výsledek není chyba. Váhy jsou nezáporné, Dijkstra je tedy korektní [L2.4] a vrátil přesně to, co slibuje výstupní specifikace slidu 16: cestu s nejmenším součtem vah ($3 < 10$). Že má vítězná cesta zároveň nejvíc hran v celém grafu, algoritmus vůbec „nevidí“. Cena a počet hran jsou dvě různá kritéria — a Dijkstra optimalizuje jen to první.
Když opravdu chci nejmenší počet hran
Zkus sám: úloha zní „najdi $s \to t$ cestu s nejmenším počtem hran“. Jak ji vyřešíš nástroji, které už máš — bez nového algoritmu?
Předefinuj váhy: polož $c(e) := 1$ pro každou hranu. Pak pro každou cestu platí
$$c(P) = \sum_{e \in P} 1 = |P|,$$cena cesty je její počet hran — a Dijkstra, který minimalizuje cenu, teď minimalizuje přesně počet hran. Jednotkové váhy jsou nezáporné, takže korektnost máme zadarmo. Tenhle speciální běh už známe: Dijkstra s jednotkovými vahami zavírá vrcholy po „vlnách“ podle počtu kroků — je to prohledávání do šířky (BFS) [L2.10].
Vzorec z minulé lekce [L2.15] teď můžeme přečíst nově: po posunu vah o $+h$ je
$$c'(P) = \underbrace{c(P)}_{\text{cena}} + h \cdot \underbrace{|P|}_{\text{počet hran}}$$— tedy směs obou kritérií s „mixážním knoflíkem“ $h$. Pro $h = 0$ optimalizuješ čistou cenu, pro obrovské $h$ (nebo pro $c \equiv 0$) prakticky čistý počet hran. Proto posun $+h$ nejkratší cestu nezachovává: potichu mění zadání úlohy. A jednotkové váhy z try-otázky výše jsou jen druhý extrém téže rovnice.
Co když je víc stejně levných nejkratších cest a já bych rád tu s nejméně hranami? Ani to Dijkstra negarantuje. Příklad: cesty $s \to a \to b \to t$ ($1+1+1 = 3$, tři hrany) a $s \to c \to t$ ($2+1 = 3$, dvě hrany). Vrcholy $b$ a $c$ mají obě značky $2$ — remíza při výběru minima, kterou pseudokód nijak nerozhoduje [L2.5]. Expanduje-li $b$ dřív, nastaví $l(t) := 3$, $p(t) := b$; následná relaxace hrany $(c,t)$ s ostrým testem ($3 > 3$ neplatí) už nic nepřepíše — a rekonstrukce z $p$ vrátí cestu o třech hranách, ačkoliv existuje stejně levná dvouhranná. (Graf k tomuhle příkladu je v řešení úlohy T01.)
Pozor: nebezpečná polopravda- „Nejkratší cesta = cesta s nejméně hranami.“ NE — „nejkratší“ v KO znamená nejmenší součet vah; počet hran je jiné kritérium a optima se mohou lišit (protipříklad výše: cena $3$ na třech hranách porazí cenu $10$ na jedné). Při čtení zadání rozlišuj shortest path (váhy) vs. minimum number of edges / fewest hops (počet hran) — druhé řešíš jednotkovými vahami.
- „Dijkstra preferuje kratší cesty v počtu hran.“ NE — počet hran do algoritmu nikde nevstupuje; ani mezi stejně levnými cestami není méně hran zaručeno (záleží na tie-breakingu [L2.5]).
Key takeaways — L2.16- Dijkstra minimalizuje cenu (součet vah), NE počet hran — počet hran v pseudokódu nikde nevystupuje. Nejlevnější cesta může mít víc hran než dražší: protipříklad $s{\to}a{\to}b{\to}t$ za $1+1+1=3$ (3 hrany) vs. přímá hrana $s{\to}t$ za $10$ (1 hrana).
- Min počet hran → všem hranám váhu $1$: pak $c(P) = |P|$ a Dijkstra minimalizuje přesně počet hran (jednotkové váhy = BFS vlna [L2.10]).
- Posun vah o $+h$ [L2.15] dává $c'(P) = c(P) + h\,|P|$ — směs obou kritérií; proto nejkratší cestu nezachovává.
- Ani mezi více stejně levnými cestami Dijkstra nezaručí nejmenší počet hran — rozhodne tie-breaking [L2.5].
- Zkouškový výrok „Dijkstra nalezne vždy nejkratší cestu s nejmenším počtem hran“ NEPLATÍ — vyvracej malým protipříkladem se dvěma cestami (levná o více hranách vs. dražší o jedné).
5 výroků a říct zda platí nebo ne. Pokud platí, dokázat, pokud ne, udělat protipříklad. Výroky typu […] „Dijkstrův algoritmus nalezne vždy nejkratší cestu s nejmenším počtem hran“)
a) Co je v zadání?
Formát „dokaž, nebo vyvrať protipříkladem“. Výrok lze číst dvěma způsoby: (i) cesta, kterou Dijkstra vrátí, má nejmenší počet hran mezi všemi $s \to t$ cestami; (ii) mezi všemi stejně levnými nejkratšími cestami vrátí Dijkstra tu s nejmenším počtem hran. Na písemce rozhodne přesné EN znění — zde vyvrátíme obě čtení (a protipříklady volíme s nezápornými vahami, ať je Dijkstra v protipříkladu korektní a debata se vede čistě o počtu hran).
b) Co k tomu budeme potřebovat?
- Tato lekce — cena vs. počet hran, hotový protipříklad i remízový příklad.
- [L2.4] Dijkstrův algoritmus (běh) — co algoritmus vrací a kdy je korektní.
- [L2.5] Pořadí expanze a tie-breaking — chování při remíze není specifikované.
c) Jak nad úlohou uvažovat?
Nejdřív si ujasni, co Dijkstra minimalizuje (jen součet vah — projdi pseudokód). Pak stavěj nejmenší možný protipříklad: dvě konkurenční $s \to t$ cesty, jedna levná s mnoha hranami, druhá drahá s jedinou hranou. Pro čtení (ii) hledej remízu: dvě stejně levné cesty s různým počtem hran a takovou geometrii, aby o $p(t)$ rozhodlo nespecifikované pořadí při výběru minima.
d) Úplné řešení (vlastní)
Výrok NEPLATÍ (v žádném z obou čtení).
Čtení (i): nalezená cesta nemá nejmenší počet hran ze všech cest. Protipříklad = graf z lekce: vrcholy $\{s,a,b,t\}$, hrany $c(s,a)=c(a,b)=c(b,t)=1$ a $c(s,t)=10$. Váhy jsou nezáporné, Dijkstra je tedy korektní a vrátí nejlevnější cestu $s \to a \to b \to t$ s cenou $3$ ($< 10$) — viz krokovaný běh v lekci ($l(t)=3$, $p(t)=b$). Cesta s nejmenším počtem hran je ale přímá hrana $s \to t$ (1 hrana vs. 3 hrany). Dijkstra tedy nalezl nejkratší (nejlevnější) cestu, která počet hran nemá nejmenší. $\blacksquare$
Čtení (ii): ani mezi stejně levnými cestami není nejmenší počet hran zaručen. Protipříklad: vrcholy $\{s,a,b,c,t\}$, hrany $c(s,a)=c(a,b)=c(b,t)=1$, $c(s,c)=2$, $c(c,t)=1$ (graf níže, pod řešením). Obě $s \to t$ cesty stojí $3$: $s{\to}a{\to}b{\to}t$ (3 hrany) i $s{\to}c{\to}t$ (2 hrany). Běh: uzavři $s$ ($0$), pak $a$ ($1$); teď mají $b$ i $c$ značku $2$ — remíza, kterou pseudokód nerozhoduje [L2.5]. Zvolí-li implementace $b$, nastaví relaxace $(b,t)$: $l(t):=3$, $p(t):=b$; při následné expanzi $c$ relaxace $(c,t)$ s ostrým testem $3 > 2+1$ neuspěje a $p(t)=b$ zůstane. Rekonstrukce z $p$ vrátí cestu o třech hranách $s{\to}a{\to}b{\to}t$, ačkoliv existuje stejně levná dvouhranná. „Vždy“ tedy neplatí — výsledek závisí na tie-breakingu. $\blacksquare$
Poznámka navíc (hodí se k ústní): výrok se stane pravdivým, omezíme-li ho na jednotkové váhy — pak $c(P)=|P|$, minimalizace ceny je minimalizace počtu hran (BFS [L2.10]). Obecný recept na „cestu s nejmenším počtem hran“ je proto: přepiš všechny váhy na $1$ a pusť Dijkstru/BFS.