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

Pořadí expanze a tie-breaking — Edge costs assignment [FOTO]

Jedna nová věc Pořadí expanze Dijkstry je čitelné přímo ze značek (uzavírá se v pořadí neklesajících $l$, remízy řeší tie-break) — a hrany, které vnitřní smyčka nikdy netestuje, jsou pro běh neviditelné. Díky tomu umíme úlohu obrátit: navrhnout váhy hran tak, aby běh Dijkstry dopadl přesně podle zadání.

Prerekvizity: [L2.4] Dijkstrův algoritmus (běh). Tam jsme si u běhů opakovaně všímali, že se vrcholy uzavírají v pořadí neklesajících značek — dnes ten slíbený postřeh povýšíme na pracovní nástroj a vytěžíme z něj celou zkouškovou úlohu Edge costs assignment (přiřazení cen hran).

Pořadí expanze čteš ze značek

Dijkstra v každé iteraci uzavře neuzavřený vrchol s nejmenší značkou. Protože uzavřená značka už nikdy neklesne a nové odhady vznikají jen přičítáním nezáporných vah k už uzavřeným značkám, uzavírají se vrcholy v pořadí neklesajících $l$ — viz [L2.4]. Pořadí expanze tedy není žádná nezávislá informace „navíc“: je svázané s hodnotami vzdáleností.

Zkus sám: v úloze T01 lekce [L2.4] vyšlo $l = (0, 4, 1, 6, 3, 7, 9, \infty)$. Dokážeš z toho zrekonstruovat pořadí přidávání do $R$, aniž bys běh opakoval?

Ano — stačí vrcholy seřadit podle výsledné značky: $0, 1, 3, 4, 6, 7, 9, \infty$ dává pořadí $1, 3, 5, 2, 4, 6, 7, 8$. Přesně to vyšlo i krokováním běhu.

Funguje to ale jednoznačně jen tehdy, když jsou všechny značky navzájem různé. Při rovnosti dvou značek pořadí z vektoru $l$ nepoznáš — a jak hned uvidíme, nepozná ho jednoznačně ani sám algoritmus.

Hrany, které běh vůbec nevidí

Druhá ingredience dneška je nenápadný detail pseudokódu ze slidu 16: vnitřní smyčka relaxuje jen hrany for w ∈ V(G) \ R. Hrana $(v,w)$ se testuje jedinkrát za celý běh — při expanzi $v$ — a pokud je v tu chvíli $w$ už uzavřené, přeskočí se bez testu. Přesně tohle v [L2.4] položilo Dijkstru na záporné hraně: hranu $(b,a)$ vedoucí do uzavřeného vrcholu už nikdo netestoval. Dnes stejný jev využijeme pozitivně. Proklikej si běh a sleduj hranu $b \to a$:

Zkus sám: co se stane s během, když váhu hrany $b \to a$ změníš z $6$ na $1$? A na $100$?

Vůbec nic. Až do expanze $b$ je běh s váhou $1$, $6$ i $100$ identický — váha $b \to a$ do té doby v ničem nefiguruje. A při expanzi $b$ je $a$ už uzavřené, takže smyčka hranu přeskočí, ať na ní stojí cokoliv. Zbytek běhu je zase identický.

Váha takové hrany je pro běh neviditelná: můžeš ji změnit na libovolnou hodnotu a pořadí expanze, vektor $l$ i vektor $p$ vyjdou stejně. (Stejně neviditelné jsou hrany vycházející z posledního uzavřeného vrcholu — při jeho expanzi už žádný neuzavřený $w$ nezbývá.)

Pozor na jemnost: hrana, která se testuje, ale nikdy žádnou značku nesníží (test ostře nevyjde), úplně volná není. Zvětšovat ji můžeš libovolně, ale zmenšit jen po určitou mez — pod ní by začala vyhrávat relaxace a běh by se změnil. Taková hrana má jen povolené rozmezí.

Remízy a tie-breaking

Řádek Find v ∈ V(G) \ R such that l(v) = min… ze slidu 16 neříká, kterého kandidáta vybrat, když je minimálních značek víc. Pravidlu, kterým se implementace při takové remíze rozhodne (např. „vezmi vrchol s nejmenším indexem“), se říká tie-breaking (rozhodování remíz) — a pseudokód žádné nepředepisuje.

Zkus sám: změň v grafu výše váhu hrany $s \to b$ ze $4$ na $1$. Jaká pořadí expanze jsou teď možná a co všechno se mezi nimi liší?

Po expanzi $s$ je $l(a) = l(b) = 1$ — remíza. Podle tie-breaku se běh větví:

  • Nejdřív $a$: pořadí $s, a, b, c$; testuje se hrana $a \to b$ ($1 > 1+2$? ne), hrana $b \to a$ se přeskočí.
  • Nejdřív $b$: pořadí $s, b, a, c$; testuje se naopak $b \to a$ ($1 > 1+6$? ne) a přeskočí se $a \to b$.

Výsledný vektor $l = (0, 1, 1, 2)$ vyjde v obou větvích stejně — vzdálenosti jsou pro nezáporné váhy jednoznačné. Liší se ale pořadí expanze a dokonce i množina testovaných (a tedy neviditelných) hran.

Proto když zkouškové zadání říká, že Dijkstra „must visit/expand the vertices in the following order“, znamená to: pořadí musí vyjít při každém tie-breaku — tvoje váhy musí zařídit, aby v okamžiku každého výběru bylo minimum jediné (samé ostré nerovnosti, žádná remíza).

Reverzní úloha: navrhni váhy

Teď úlohu otočíme — přesně tak je postavená zkoušková úloha Edge costs assignment. Zadané je pořadí expanze, výsledná nejkratší cesta a strop na její cenu; hledají se váhy. Recept:

  1. Pořadí → značky. Pořadí expanze znamená ostře rostoucí posloupnost značek (remízy nesmí nastat): $0 = l(v_1) < l(v_2) < \dots$ Zvol konkrétní malá čísla, např. $0, 1, 2, 3, \dots$ — strop na cenu cesty hlídej u cílového vrcholu.
  2. Značky → stromové hrany. Každou značku musí někdo „doručit“: pro každý vrchol $w$ vyber hranu $(v, w)$ z dříve uzavřeného $v$ a nastav $c(v,w) = l(w) - l(v)$. To budou hrany stromu nejkratších cest — vektor $p$ musí odpovídat požadované cestě.
  3. Zbylé hrany nesmí škodit. Každá další hrana, kterou běh testuje, nesmí žádnou značku podlézt ani remizovat (remíza při relaxaci znamená, že požadované $p$ není vynucené — ostrý test z [L2.3] při rovnosti nechá stát dřívější $p$ a na nespecifikovaný tie-breaking se nelze spolehnout; remíza značek rozbije jednoznačnost výběru). Nastav ji dost velkou a ověř celý běh.
  4. Volné hrany. Hrany, jejichž relaxace se nikdy neprovede (vedou do vrcholu uzavřeného dřív, než se expanduje jejich začátek), můžeš měnit libovolně — to je v úloze druhá otázka.
Pozor: „neleží na nejkratší cestě“ ≠ „lze měnit libovolně“
Key takeaways — L2.5
T01 Edge costs assignment FOTO checkpoint zdroj: zkouška KO 25.05.2026 (7 b.); dříve 02.06.2021; bank #12. Pozn.: oba přepisy kreslí hranu mezi $d$ a $t$ jako $t \to d$, jejich ruční odpovědi se ale liší: 25.05.2026 uvádí volné jen $a \to d$ a $c \to d$ (odpovídá orientaci $d \to t$), 02.06.2021 navíc i hranu $d$–$t$ (konzistentní s $t \to d$). Graf i odpověď níže přebíráme z banky (#12), která má orientaci $d \to t$.
Assignment (original, EN)

Consider the graph above. Assign edge weights from $\mathbb{N} = \{1, 2, \dots\}$ to each edge so that (multiple edges can be assigned the same weight):

  1. Dijkstra algorithm searching the shortest path from vertex $s$ to vertex $t$ must visit/expand the vertices in the following order: $s, b, d, a, c, t$.
  2. The resulting shortest path is $s - a - t$.
  3. The cost of the shortest path (sum of path's edge weights) is $\leq 5$.

After you assigned the edge weights such that conditions 1–3 hold, mark the edges whose value can be changed to any value from $\mathbb{N}$ such that a run of Dijkstra algorithm still necessarily results in satisfying conditions 1–3.

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 (na zkoušce na ni budeš mít zhruba 15–20 minut; je za 7 bodů). Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.

a) Co je v zadání?

Orientovaný graf s vrcholy $s, a, b, c, d, t$ a osmi hranami bez vah — váhy z $\mathbb{N}$ navrhuješ ty. Úloha má dvě části: ① přiřadit váhy tak, aby Dijkstra ze $s$ expandoval přesně v pořadí $s, b, d, a, c, t$, výsledná nejkratší cesta byla $s\!-\!a\!-\!t$ a její cena nejvýš $5$; ② u hotového přiřazení označit hrany, které lze přepsat na libovolnou hodnotu z $\mathbb{N}$, aniž by se podmínky 1–3 mohly rozbít (slovo necessarily: musí to vyjít při každém tie-breaku).

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Jdi přesně podle receptu z výkladu. Pořadí $s, b, d, a, c, t$ znamená ostře rostoucí značky $0 = l(s) < l(b) < l(d) < l(a) < l(c) < l(t)$, a podmínka 3 přidává $l(t) \le 5$ — takže se nabízí rovnou $0, 1, 2, 3, 4, 5$. Pak si rozmysli, kdo komu značku doručí: jediná hrana do $b$ je $s \to b$, do $d$ vedou tři, ale v okamžiku uzavření $d$ je z nich expandované jen $b$… Podmínka 2 říká, že $l(t)$ musí doručit hrana $a \to t$ (tj. $p(t) = a$), s cenou cesty $c(s,a) + c(a,t) = l(t)$. Nakonec prověř hrany mimo strom: jak velké musí být $c(d,t)$, aby relaxace z $d$ cestu $s\!-\!a\!-\!t$ nepodlezla ani neremizovala? A volné hrany hledej podle pravidla z výkladu: které hrany vedou do vrcholu, jenž se uzavře dřív, než se expanduje jejich začátek?

d) Úplné řešení

① Návrh značek. Pořadí $s, b, d, a, c, t$ + strop $5$ → zvol $l(s)=0$, $l(b)=1$, $l(d)=2$, $l(a)=3$, $l(c)=4$, $l(t)=5$.

② Stromové hrany (kdo značku doručí): $l(b)$ jedině hranou $s \to b$ → $c(s,b)=1$. $l(d)$ může v čase uzavření $d$ doručit jen $b$ → $c(b,d) = 2-1 = 1$. $l(a)$ jedině hranou $s \to a$ → $c(s,a)=3$. $l(c)$ jedině hranou $b \to c$ → $c(b,c) = 4-1 = 3$. $l(t)$ musí kvůli podmínce 2 doručit $a \to t$ → $c(a,t) = 5-3 = 2$; cena cesty $3+2 = 5 \le 5$ ✓.

③ Zbylé hrany nesmí škodit. Hrana $d \to t$ se testuje při expanzi $d$ (3. iterace) a nastaví $l(t) = 2 + c(d,t)$. Aby pak relaxace $a \to t$ ještě ostře vyhrála ($2 + c(d,t) > 3 + 2 = 5$), musí být $c(d,t) \ge 4$. Menší hodnoty selžou:

  • $c(d,t) = 3$ → $l(t) = 5$ a test $5 > 5$ nevyjde — ostrá relaxace z [L2.3] nechá $p(t) = d$ a výsledná cesta je $s\!-\!b\!-\!d\!-\!t$: podmínka 2 padá. (Přesně tohle míní poznámka „necessarily“ — s jiným, „vstřícnějším“ tie-breakingem při rovnosti by to náhodou vyjít mohlo, ale jistě ne.)
  • $c(d,t) = 2$ → $l(t) = 4$: remíza s $l(c)$ při výběru 5. iterace, pořadí není vynucené; navíc nejkratší cesta je $s\!-\!b\!-\!d\!-\!t$. Padá 1 i 2.
  • $c(d,t) = 1$ → $l(t) = 3$: remíza s $l(a)$ už ve 4. iteraci. Padá 1.

Zvolíme tedy např. $c(d,t) = 4$. Hrany $a \to d$ a $c \to d$ běh nikdy netestuje (viz ⑤), jejich hodnota je libovolná — pro konkrétnost třeba $1$.

Jedno platné přiřazení (shodné s bankou):

$$c(s,a)=3,\quad c(s,b)=1,\quad c(a,t)=2,\quad c(b,d)=1,\quad c(b,c)=3,\quad c(d,t)=4,$$

a $c(a,d) = x$, $c(c,d) = y$ libovolné ($x, y \in \mathbb{N}$).

④ Ověření během (každý výběr má jediné minimum → pořadí platí pro každý tie-break):

  • It 1: uzavři $s\,(0)$; $l(a):=3$, $l(b):=1$.
  • It 2: min je $b\,(1)$; $l(d):=2$, $p(d):=b$; $l(c):=4$, $p(c):=b$.
  • It 3: min je $d\,(2 < 3)$; $l(t):=2+4=6$, $p(t):=d$.
  • It 4: min je $a\,(3 < 4)$; $(a,t)$: $6 > 3+2=5$ → $l(t):=5$, $p(t):=a$; $(a,d)$: $d \in R$, netestuje se.
  • It 5: min je $c\,(4 < 5)$; $(c,d)$: $d \in R$, netestuje se.
  • It 6: zbývá $t\,(5)$, konec.

Pořadí expanze $s, b, d, a, c, t$ ✓ (značky $0,1,2,3,4,5$ ostře rostou); couváním po $p$: $p(t)=a$, $p(a)=s$ → cesta $s\!-\!a\!-\!t$ ✓ s cenou $3+2 = 5 \le 5$ ✓.

⑤ Volné hrany. $d$ se uzavírá ve 3. iteraci — dřív, než se expanduje $a$ (4. it.) i $c$ (5. it.). Hrany $a \to d$ a $c \to d$ proto vnitřní smyčka (for w ∈ V(G) \ R) nikdy netestuje a běh je na jejich hodnotě nezávislý:

$$\boxed{a \to d \quad\text{a}\quad c \to d}$$

Žádná další hrana volná není: $c(s,b)$, $c(b,d)$, $c(s,a)$, $c(b,c)$, $c(a,t)$ určují značky (jejich změna posune pořadí nebo cenu cesty) a $c(d,t)$ je svázané mezí $c(d,t) \ge 4$ — viz ③ (to je přesně polopravda z červeného boxu: $d \to t$ na nejkratší cestě neleží, a přesto volné není).

Krokovaná verze ověřovacího běhu (pozor, spoiler na řešení — nejdřív si úlohu vyřeš na papír):

← Předchozí L2.4 · Dijkstrův algoritmus (běh)