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

VYVRCHOLENÍ: Dangerous adventure [FOTO]

Jedna nová věc Zkoušková úloha Dangerous adventure kombinuje oba triky z minulých lekcí v jednom řetězu: pravděpodobnosti smrti na hranách i vrcholech → přepiš na pravděpodobnosti přežití → dostaň je všechny na hrany (split [L2.6], nebo složení do vstupních hran) → $-\log$ [L2.7] → Dijkstra → zpětný převod na pravděpodobnost.

Prerekvizity: [L2.6] Split vrcholu a [L2.7] Transformace −log. Obě minulé lekce na tuhle úlohu mířily — dnes je čas oba triky zřetězit a celé to spočítat na papír: jde o druhý FOTO checkpoint kapitoly (zadáno na zkoušce 25. 5. 2026 v obou termínech, dříve i 2023).

Mapa ostrova

Dobrodruh má mapu ostrova: start $s$, poklad $t$ a křižovatky $V$, mezi nimi jednosměrné spoje $E$ — orientovaný souvislý graf. Na každé křižovatce $i \in V$ (kromě $s$ a $t$) ho s pravděpodobností $b_i$ zabijí bandité; na každém spoji $j \in E$ ho s pravděpodobností $l_j$ sežere lev. Všechny události jsou navzájem nezávislé (unrelated) a v čase se nemění. Cíl: dostat se z $s$ do $t$ a minimalizovat pravděpodobnost smrti.

Zkus sám: zadání chce minimalizovat pravděpodobnost smrti. Spočítej pravděpodobnost, že dobrodruh přežije cestu $s \to a \to t$ v mapě výše. Co všechno musí přežít?

Musí přežít lva na spoji $s \to a$ (pravděpodobnost $1 - 0{,}5 = 0{,}5$), a bandity na křižovatce $a$ ($1 - 0{,}875 = 0{,}125$), a lva na spoji $a \to t$ ($0{,}5$). Díky nezávislosti se pravděpodobnosti přežití násobí:

$$P(\text{přežije } s \to a \to t) = 0{,}5 \cdot 0{,}125 \cdot 0{,}5 = 0{,}03125.$$

A protože $P(\text{smrt}) = 1 - P(\text{přežití})$, je minimalizace pravděpodobnosti smrti totéž co maximalizace pravděpodobnosti přežití — se součinem se pracuje líp, takže od teď maximalizujeme přežití. Obecně: cesta přežije s pravděpodobností $\prod_{j \in \text{spoje}} (1 - l_j) \cdot \prod_{i \in \text{křižovatky}} (1 - b_i)$.

Zkus sám: spočítej i přežití cesty $s \to c \to t$. A porovnej s rozhodnutím, kdyby na ostrově byli jen lvi (bez banditů) — mění bandité vítěze?

Přes $c$: $0{,}25 \cdot 1 \cdot 0{,}5 = 0{,}125$ (na $c$ bandité nejsou, $b_c = 0$). Srovnání:

  • Jen lvi: přes $a$: $0{,}5 \cdot 0{,}5 = 0{,}25$; přes $c$: $0{,}25 \cdot 0{,}5 = 0{,}125$ → vyhrává $a$.
  • Lvi + bandité: přes $a$: $0{,}03125$; přes $c$: $0{,}125$ → vyhrává $c$.

Bandité rozhodnutí převrátí — stejný jev jako u cen vrcholů v [L2.6], jen v pravděpodobnostním kabátě. Ignorovat je nelze.

Dva triky, jedna úloha

Zkus sám: proti obyčejnému shortest path z [L2.4] tu stojí hned tři překážky. Najdeš je? A které lekce je řeší?
  1. Hodnota cesty je součin a maximalizujeme → transformace $-\log$ z [L2.7] (součin → součet, max → min).
  2. Pravděpodobnosti sedí i na vrcholech (bandité na křižovatkách) → split vrcholu z [L2.6], který dostane hodnotu vrcholu na vlastní hranu.
  3. Dijkstra chce nezáporné váhy → zadarmo: všechna přežití jsou pravděpodobnosti $\in (0,1]$, takže $-\log p \ge 0$ [L2.7].

Nic nového se učit nemusíš — celá úloha je zřetězení dvou hotových triků.

Recept tedy je:

  1. Smrt → přežití: na spoji $j$ přežiješ s pravděpodobností $1 - l_j$, na křižovatce $i$ s pravděpodobností $1 - b_i$; pro start a poklad polož $b_s = b_t = 0$ (tam podle zadání bandité nečíhají).
  2. Split křižovatek [L2.6]: $v \to v_1, v_2$; nová hrana $v_1 \to v_2$ nese přežití banditů $1 - b_v$; vstupy do $v_1$, výstupy z $v_2$. Teď sedí všechny pravděpodobnosti na hranách.
  3. Transformace [L2.7]: každé hraně dej váhu $c(e) := -\log p(e)$, kde $p(e)$ je její pravděpodobnost přežití — váhy jsou nezáporné.
  4. Dijkstra [L2.4] z $s$ do $t$ (proč tentokrát $s$ a $t$ nesplitujeme — viz try níže).
  5. Zpětný převod: přežití optimální cesty $S = b^{-l(t)}$ a odpověď na otázku zadání $P(\text{smrt}) = 1 - S$. Pozor na kolizi značek: zde $b$ je základ logaritmu (ten, kterým jsi logaritmoval) — nesouvisí s pravděpodobností banditů $b_i$; a $l(t)$ je vzdálenost vrácená Dijkstrou [L2.4] — nesouvisí se lvy $l_j$.
Zkus sám: v [L2.6] jsme splitovali všechny vrcholy včetně $s$ a $t$ a hledali cestu $s_1 \to t_2$. Proč tady $s$ a $t$ splitovat nemusíme?

Zadání říká, že bandité jsou na každé křižovatce „except for $s$ and $t$“ — start a poklad žádné riziko nenesou, tedy $b_s = b_t = 0$ a přežití $1 - b_s = 1 - b_t = 1$. Split by jim přidal hranu s vahou $-\log 1 = 0$: není to chyba, jen zbytečnost. Hledá se obyčejná cesta $s \to t$.

Zkus sám: záleží na pořadí kroků ② (split) a ③ ($-\log$)?

Ne. Split jen přemístí pravděpodobnost vrcholu na vlastní hranu a $-\log$ se pak aplikuje na každou hranu zvlášť; díky $-\log(xy) = -\log x - \log y$ vyjde součet vah každé cesty stejně, ať transformuješ před splitem (váhy vrcholů $-\log(1-b_i)$ a pak je splituješ jako „ceny vrcholů“ z [L2.6]), nebo po něm.

Celý postup na příkladu

Mapa z úvodu po krocích ① a ②: smrt přepsaná na přežití a křižovatky $a, c$ splitnuté — všechny pravděpodobnosti teď sedí na hranách.

Krok ③, váhy $c(e) = -\log_2 p(e)$ (přežití jsou mocniny $\tfrac12$, takže základ 2 dá hezká celá čísla: $0{,}5 \to 1$, $0{,}25 \to 2$, $0{,}125 \to 3$, $1 \to 0$):

Zkus sám: jakou délku mají obě $s$–$t$ cesty v transformovaném grafu a čemu odpovídají v pravděpodobnostech?

Přes $a$: $1 + 3 + 1 = 5 = -\log_2 0{,}03125$; přes $c$: $2 + 0 + 1 = \mathbf{3} = -\log_2 0{,}125$. Délka každé cesty je přesně $-\log_2$ jejího přežití — transformace zachovává hodnoty, takže nejkratší cesta = nejbezpečnější trasa.

Krok ④, běh Dijkstry [L2.4] na transformovaném grafu, a krok ⑤, zpětný převod:

Odpověď pro dobrodruha: jdi $s \to c \to t$; přežiješ s pravděpodobností $S = 2^{-l(t)} = 2^{-3} = 0{,}125$ a zemřeš s pravděpodobností $1 - 0{,}125 = 0{,}875$. (Ano, i optimální trasa je dost vražedná — ale pořád 4× lepší než přes $a$.)

Elegantnější zápis: složit bandity do vstupních hran

Vzorové řešení z banky úloh split vůbec nekreslí — využije poznámku z [L2.6], že cenu vrcholu lze složit do jeho vstupních hran, když $s$ a $t$ žádnou cenu nenesou. Jeden krok $u \to v$ znamená přežít spoj i bandity v cílovém vrcholu, takže s $b_s = b_t = 0$ stačí každé původní hraně dát rovnou váhu

$$c'(u,v) := -\log\bigl((1 - l_{uv})(1 - b_v)\bigr) = -\log(1 - l_{uv}) - \log(1 - b_v).$$

Funguje to, protože každá $s$–$t$ cesta vstoupí do každé navštívené křižovatky právě jednou (právě jednou tedy zaplatí její bandity), do $s$ nevstupuje nikdy a vstup do $t$ je s $b_t = 0$ zadarmo. Graf se nezvětší — žádné nové vrcholy ani hrany.

Zkus sám: spočítej $c'(u,v)$ pro všechny čtyři hrany našeho příkladu (základ 2) a ověř, že délky obou cest vyjdou stejně jako po splitu.

$c'(s,a) = -\log_2(0{,}5 \cdot 0{,}125) = -\log_2 0{,}0625 = 4$ (spoj i bandité v $a$); $c'(a,t) = -\log_2(0{,}5 \cdot 1) = 1$; $c'(s,c) = -\log_2(0{,}25 \cdot 1) = 2$; $c'(c,t) = -\log_2(0{,}5 \cdot 1) = 1$. Délky: přes $a$: $4 + 1 = 5$ ✓, přes $c$: $2 + 1 = 3$ ✓ — přesně jako v grafu po splitu. Obě cesty k cíli (split i složení) jsou u zkoušky plnohodnotné; split je mechaničtější (funguje vždy, i kdyby $s$ a $t$ cenu nesly), složení je rychlejší na zápis.

Složitost na míru zadání: $O(|E| \log |V|)$

Zadání výslovně chce složitost $O(|E| \times \log |V|)$. To je Dijkstra s prioritní frontou implementovanou binární haldou (binary heap): každá z $O(|E|)$ relaxací stojí jednu operaci haldy, tj. $O(\log |V|)$. (V [L2.4] jsme uváděli $O(n^2)$ a $O(m + n\log n)$ — binární halda je třetí, na zkoušce nejcitovanější varianta.) Split graf nezkazí: má nejvýš $2|V| + 2$ vrcholů a $|E| + |V|$ hran, asymptotika se nemění; složení do vstupních hran graf nemění vůbec. Důkaz, proč Dijkstra na nezáporných vahách funguje, patří do kapitoly K3 — tady stačí, že náš převod jeho předpoklad splňuje.

Pozor: tři klasické chyby v Dangerous adventure
Key takeaways — L2.8
T01 Dangerous adventure FOTO checkpoint zdroj: zkouška KO 25.05.2026 (oba termíny) = task bank #16; dříve zkoušky 2023
Assignment (original, EN)

“An adventurer has a map of the island with a starting point $s$, treasure location $t$ and set of crossroads $V$. There is a set of one-way connections $E$, each connection connecting either two crossroads, starting point and crossroad or crossroad and treasure location. (Think of a directed connected graph with a starting point, treasure location and crossroads as vertices and connections between them as edges.) The adventurer knows that at each crossroad $i \in V$ (except for $s$ and $t$), there is a probability $b_i$ that he will be killed by bandits. He also knows that at each existing connection $j \in E$, there is a probability $l_j$ that he will be eaten by a lion. All probabilities are unrelated to each other, and they don't change with time. The adventurer wants to get from the starting point to the treasure location while minimizing the probability of dying.

Help the adventurer to formulate this as a Shortest Path Problem. Describe how he can calculate his survival probability using the optimal route in $O(|E| \times \log |V|)$ time complexity ($|E|$ represents the number of edges and $|V|$ the number of vertices in the graph).”

FOTO checkpoint

Tuhle úlohu vyřeš celou NA PAPÍR — od prázdného listu, bez koukání do lekce ani do řešení, ideálně na čas (orientačně ~15–20 minut — přesný limit zkoušky doložený není, ale při 6 úlohách na test víc mít nebudeš). Napiš převod (vzorce + zdůvodnění nezápornosti), algoritmus se složitostí a zpětný výpočet pravděpodobnosti přežití. Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.

a) Co je v zadání?

Orientovaný souvislý graf: start $s$, poklad $t$, křižovatky $V$, jednosměrné spoje $E$. Pravděpodobnost smrti banditou $b_i$ na každé křižovatce (na $s$ a $t$ ne), pravděpodobnost sežrání lvem $l_j$ na každém spoji; vše nezávislé a neměnné v čase. Úkol má dvě části: ① formulovat hledání trasy minimalizující pravděpodobnost smrti jako Shortest Path Problem (tj. popsat převod — konkrétní čísla v zadání nejsou) a ② popsat, jak z optimální trasy spočítat pravděpodobnost přežití, to vše v čase $O(|E| \log |V|)$.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Projdi recept z výkladu otázkami: Co přesně se po cestě násobí a proč (nezávislost)? Jak se zbavíš banditů na vrcholech — split, nebo složení do vstupních hran (a co k tomu druhému potřebuješ vědět o $s$ a $t$)? Proč jsou váhy po $-\log$ nezáporné a proč na tom Dijkstrovi záleží? Která implementace Dijkstry dá přesně $O(|E| \log |V|)$? A nakonec: zadání se ptá na survival probability — jakým vzorcem ji z výsledku $l(t)$ (nebo z hran optimální trasy) dostaneš?

d) Úplné řešení

Převod na Shortest Path. Minimalizovat pravděpodobnost smrti = maximalizovat pravděpodobnost přežití. Polož $b_s = b_t = 0$ (start ani poklad bandity nepřidávají). Jeden krok $u \to v$ dobrodruh přežije, právě když přežije spoj i příchod do $v$; díky nezávislosti s pravděpodobností $(1 - l_{uv})(1 - b_v)$. (Doplněk jednokrokové pravděpodobnosti smrti $q_{uv} = l_{uv} + b_v - l_{uv} b_v$.) Pro cestu $P = (s = v_0, v_1, \ldots, v_k = t)$ tedy

$$S(P) = \prod_{r=0}^{k-1} (1 - l_{v_r v_{r+1}})(1 - b_{v_{r+1}}),$$

a hledáme $\arg\max_P S(P)$. Logaritmus je rostoucí (zachová vítěze) a mění součin na součet; minus otáčí max na min [L2.7]. Definuj proto novou délku hrany

$$c'(u,v) := -\log\bigl((1 - l_{uv})(1 - b_v)\bigr) = -\log(1 - l_{uv}) - \log(1 - b_v).$$

Pak pro každou cestu $\sum_{(u,v) \in P} c'(u,v) = -\log S(P)$, takže nejbezpečnější trasa = nejkratší $s$–$t$ cesta podle $c'$. Váhy jsou nezáporné: $(1 - l_{uv})(1 - b_v) \in (0,1] \Rightarrow c'(u,v) \ge 0$; je-li některé přežití $0$ (tj. $l_{uv} = 1$ nebo $b_v = 1$), hranu odstraň, případně jí dej délku $+\infty$.

Ekvivalentní varianta přes split [L2.6] (takhle to řešil i dochovaný písemkový zápis): každou křižovatku $v$ rozděl na $v_1, v_2$ s hranou $v_1 \to v_2$ délky $-\log(1 - b_v)$, vstupy do $v_1$, výstupy z $v_2$, původní spoje s délkou $-\log(1 - l_j)$; hledej cestu $s \to t$. Graf má $\le 2|V| + 2$ vrcholů a $|E| + |V|$ hran, asymptotika se nezmění.

Algoritmus a složitost. Váhy jsou nezáporné, takže pusť Dijkstru [L2.4] z $s$ do $t$ s prioritní frontou (binární haldou): $O(|E| \log |V|)$, přesně jak chce zadání.

Výpočet pravděpodobnosti přežití. Pro vrácenou optimální trasu $P^*$ je

$$S(P^*) = \prod_{(u,v) \in P^*} (1 - l_{uv})(1 - b_v) = b^{-l(t)} \quad (\text{základ } b \text{ logaritmu}),$$

tj. buď vynásob přežití podél trasy v původním grafu, nebo umocni výsledek Dijkstry. Pravděpodobnost smrti na optimální trase je $1 - S(P^*)$.

Krátká zkoušková odpověď (takto stačí): polož $b_s = b_t = 0$ a $c'(u,v) = -\log((1-l_{uv})(1-b_v))$; pak $\sum_{(u,v) \in P} c'(u,v) = -\log S(P)$, takže minimalizace transformované délky = maximalizace přežití, váhy jsou nezáporné díky $(1-l_{uv})(1-b_v) \in (0,1]$. Pusť Dijkstru s binární haldou — $O(|E| \log |V|)$ — a vrať $S(P^*) = \prod_{(u,v)\in P^*}(1-l_{uv})(1-b_v)$, smrt $= 1 - S(P^*)$.

← Předchozí L2.7 · Transformace součinu na součet: −log