Split vrcholu (cena na vrcholu → na hraně)
Prerekvizity: [L2.4] Dijkstrův algoritmus (běh). Dijkstra (a vlastně celá kapitola zatím) zná ceny jen na hranách. Dnes se naučíme jediný, ale velmi užitečný modelovací trik, kterým mu podstrčíme i ceny na vrcholech.
Když platíš i za vrcholy
Slide 5 přednášky („Similar Problems“) zavádí variantu node-weighted shortest path (nejkratší cesta s váhami na vrcholech): váhy mohou sedět na vrcholech, nebo na vrcholech i hranách, a váha cesty je součet vah hran a vah vrcholů podél cesty. Prakticky: mýto na každé křižovatce, zdržení v každém uzlu sítě, poplatek za každé překladiště — platí se nejen za přesun, ale i za průchod místem.
Zkus sám: najdi v grafu výše nejkratší cestu $s \to t$ nejdřív jen podle vah hran a pak podle vah hran i vrcholů. Vyjde stejná?
Jen podle hran vyhrává horní cesta přes $a$: $2 + 2 = 4 < 3 + 3 = 6$.
S vrcholy je to naopak. Přes $a$: hrany $4$ + vrcholy $w(s) + w(a) + w(t) = 1 + 5 + 2 = 8$, celkem $\mathbf{12}$. Přes $b$: hrany $6$ + vrcholy $1 + 1 + 2 = 4$, celkem $\mathbf{10}$ — nejkratší je dolní cesta přes $b$.
Ceny vrcholů tedy umí rozhodnutí převrátit — ignorovat je nelze a Dijkstra z [L2.4], jak ho známe, s nimi neumí pracovat. Potřebujeme je do grafu „zabudovat“.
Trik: rozdělit vrchol
Zkus sám: napadá tě úprava grafu, po které ceny vrcholů „uvidí“ i algoritmus, který zná jen ceny hran?
První přirozený nápad: přičti $w(v)$ ke každé hraně vstupující do $v$. Každá cesta projde vrcholem $v$ právě jednou a právě jednou vstupní hranou, takže se $w(v)$ započítá správně jednou. Skoro to funguje — až na start: vrchol $s$ na cestě žádnou vstupní hranou nemá, takže $w(s)$ nezaplatíš nikdy (a u symetrické varianty „přičti k výstupním“ zase vypadne $w(t)$). Pro porovnání všech $s$–$t$ cest je to jen společná konstanta, ale výsledná hodnota je špatně a sčítání dvou informací do jedné váhy je nepřehledné.
Přednáška proto používá čistší standard: cenu vrcholu nechat na vlastní hraně. Vrchol rozdělíme.
Trik ze slidu 5 — node splitting (rozdělení/split vrcholu) — má tři pravidla:
- Nahraď každý vrchol $v$ původního grafu dvojicí vrcholů $v_1$ a $v_2$ a spoj je hranou $v_1 \to v_2$ s váhou rovnou váze vrcholu $v$.
- Hrana, která do $v$ vstupovala, nyní vstupuje do $v_1$.
- Hrana, která z $v$ vycházela, nyní vychází z $v_2$.
Lokálně to vypadá takhle (okolí jednoho vrcholu $v$ s cenou $5$; sousedé $a, b, c, d$ se splitují úplně stejně, tady je necháváme vcelku kvůli přehlednosti):
Projít vrcholem $v$ teď nejde jinak než po hraně $v_1 \to v_2$ — z $v_1$ žádná jiná hrana nevede. Kdo vrcholem projde, cenu $w(v)$ zaplatí; kdo neprojde, neplatí nic. Přesně sémantika „váha vrcholů podél cesty“.
Celý graf po splitu
Takhle dopadne split celého grafu z úvodu (modré hrany jsou nové — nesou ceny vrcholů):
Zkus sám: jaká je v novém grafu váha nejkratší cesty $s_1 \to t_2$? Souhlasí s ručním výpočtem z první try-otázky?
Přes $b$: $s_1 \xrightarrow{1} s_2 \xrightarrow{3} b_1 \xrightarrow{1} b_2 \xrightarrow{3} t_1 \xrightarrow{2} t_2$, váha $1+3+1+3+2 = \mathbf{10}$. Přes $a$: $1+2+5+2+2 = \mathbf{12}$.
Souhlasí: stejné hodnoty jako „hrany + vrcholy“ v původním grafu, vítězí cesta přes $b$. Každá hodnota původní úlohy teď sedí na právě jedné hraně — nic se neztratilo, nic nepřibylo. A protože jsou všechny váhy nezáporné, najde tuhle cestu Dijkstra [L2.4]; výslednou cestu v původním grafu přečteš prostě smazáním indexů: $s_1 s_2 b_1 b_2 t_1 t_2 \to s\!-\!b\!-\!t$.
Zkus sám: původní graf měl $n$ vrcholů a $m$ hran. Kolik má graf po splitu? Zpomalí se tím Dijkstra?
Každý vrchol se zdvojí a přibude jedna hrana na vrchol: nový graf má $2n$ vrcholů a $m + n$ hran. Dijkstra v $O(n^2)$ [L2.4] tedy běží v $O((2n)^2) = O(4n^2)$ — konstanta, řádově se nic nemění.
Pozor: směr a konce nesmíš zaměnit- Vstupy do $v_1$, výstupy z $v_2$ — ne naopak. Dvě různé chyby, dva různé průšvihy: a) při prohození (vstupy do $v_2$, výstupy z $v_1$) cesta v $v_2$ uvízne — z $v_2$ nic nevede, do $v_1$ nic nepřichází, průchod vrcholem přestane existovat a graf se rozpadne; b) při zapomenutém přepojení (vstupy i výstupy necháš na témže vrcholu z dvojice) cesta projde, ale hranu $v_1 \to v_2$ mine a cenu $w(v)$ obejde.
- Hledej cestu $s_1 \to t_2$. Definice ze slidu počítá váhy všech vrcholů podél cesty, včetně koncových — start v $s_2$ nebo cíl v $t_1$ by ceny $w(s)$, $w(t)$ vynechal. (Pozorování navíc: pokud konkrétní úloha za koncové vrcholy neplatí, můžeš to zařídit právě volbou $s_2 \to t_1$.)
K čemu to budeVe zkouškové úloze Dangerous adventure [L2.8] sedí „ceny“ (pravděpodobnosti přežití) na hranách i vrcholech. Split je jeden ze dvou korektních způsobů, jak to zvládnout — druhý je složit cenu vrcholu do jeho vstupních hran, což tam funguje exaktně právě proto, že zadání za $s$ a $t$ neplatí (stejný efekt jako volba $s_2 \to t_1$ z poznámky výše); vzorové řešení jde touhle druhou cestou. Druhou půlku úlohy, převod součinu pravděpodobností na součet přes $-\log$, přidá příští lekce [L2.7] Transformace součinu na součet: −log.
Key takeaways — L2.6- Split vrcholu: $v \to v_1, v_2$ + hrana $v_1 \to v_2$ s váhou $w(v)$; hrany vstupující do $v$ vedou do $v_1$, hrany vycházející z $v$ vycházejí z $v_2$.
- Hledá se cesta $s_1 \to t_2$: cesty si odpovídají 1:1 a váha (hrany + vrcholy) se přesně zachová — výsledek přečteš smazáním indexů.
- Nový graf má $2n$ vrcholů a $m + n$ hran — asymptotika Dijkstry se nemění; nezáporné ceny hran i vrcholů dají nezáporné váhy, takže Dijkstra [L2.4] funguje.
- Ve zkouškové úloze Dangerous adventure [L2.8] se s transformací $-\log$ [L2.7] kombinuje split, nebo složení ceny vrcholu do vstupních hran (jde to, protože $s$ a $t$ tam cenu nenesou).
When the nodes are weighted, or both nodes and edges are weighted, the weight of the path is the sum of the edges and the nodes weights along this path. This can be transformed to the weighted edges case as follows:
- Replace every node $v$ from the original graph by the pair of nodes $v_1$ and $v_2$ and connect them by an edge with weight equal to the weight of node $v$.
- the edge entering node $v$ now enters $v_1$,
- the edge leaving node $v$ now leaves $v_2$.
Study task: formulate the resulting ordinary edge-weighted shortest-path instance.
a) Co je v zadání?
Studijní úloha z banky: samotný trik (tři pravidla splitu) je v zadání darovaný. Tvoje práce je převod dotáhnout do formální instance obyčejné úlohy o nejkratší cestě — tj. přesně zapsat, jaký graf, jaké váhy a mezi kterými vrcholy předáš algoritmu. U ústní zkoušky se navíc hodí umět říct, proč převod funguje.
b) Co k tomu budeme potřebovat?
- Tato lekce — pravidla splitu a korespondence cest.
- [L2.1] Záporné váhy ano, záporné cykly ne — jak vypadá instance shortest path (digraf, váhy $c$, vrcholy $s, t$).
- [L2.4] Dijkstrův algoritmus (běh) — kdo výslednou instanci vyřeší a za jakých podmínek.
c) Jak nad úlohou uvažovat?
„Formulovat instanci“ = odpovědět na čtyři otázky: Jaká je množina vrcholů? Jaká je množina hran a jejich váhy? Odkud? Kam? Kontrola správnosti: každý kus dat původní úlohy (váha každé hrany, váha každého vrcholu) musí v nové instanci sedět na právě jedné hraně — a každá $s$–$t$ cesta původního grafu musí mít v novém grafu protějšek se stejnou váhou (a naopak, žádné nové cesty nesmí vzniknout).
d) Úplné řešení
Vstup původní úlohy: digraf $G$, váhy hran $c : E(G) \to \mathbb{R}$ (pokud jsou váhy jen na vrcholech, polož $c \equiv 0$), váhy vrcholů $w : V(G) \to \mathbb{R}$, vrcholy $s, t \in V(G)$; $n = |V(G)|$, $m = |E(G)|$.
Výsledná instance (digraf $G'$, váhy $c'$, počáteční a koncový vrchol):
$$V(G') = \{\, v_1, v_2 : v \in V(G) \,\} \qquad (2n \text{ vrcholů}),$$
$$E(G') = \underbrace{\{\, (v_1, v_2) : v \in V(G) \,\}}_{\text{hrany vrcholů}} \;\cup\; \underbrace{\{\, (u_2, v_1) : (u, v) \in E(G) \,\}}_{\text{původní hrany}} \qquad (n + m \text{ hran}),$$
$$c'(v_1, v_2) = w(v), \qquad c'(u_2, v_1) = c(u, v),$$
a hledá se nejkratší cesta z $\,s_1$ do $\,t_2$ v $G'$ s váhami $c'$.
Proč to odpovídá. Z vrcholu $v_1$ vede jediná hrana, a to $(v_1, v_2)$ — každá cesta v $G'$ proto střídá „hrany vrcholů“ a „původní hrany“: $s_1, s_2, x_1, x_2, \dots, t_1, t_2$. Smazáním indexů z ní vznikne $s$–$t$ cesta v $G$ a naopak každá $s$–$t$ cesta v $G$ se tímto střídáním jednoznačně zvedne do $G'$ — korespondence je 1:1. Váhy si odpovídají přesně: cesta v $G'$ posbírá $c(u,v)$ za každou hranu cesty a $w(v)$ za každý vrchol podél ní (včetně $s$ a $t$ díky hranám $(s_1,s_2)$ a $(t_1,t_2)$), což je přesně definice váhy node-weighted cesty. Nejkratší cesty si tedy odpovídají i s hodnotou.
Kdo to vyřeší. Jsou-li $c \ge 0$ a $w \ge 0$, jsou i váhy $c'$ nezáporné a instanci vyřeší Dijkstra [L2.4] v čase $O((2n)^2) = O(n^2)$.
Konkrétní provedení převodu vidíš na dvojici obrázků ve výkladu (graf z úvodu → graf po splitu): nejkratší cesta $s_1 \to t_2$ má váhu $10$ a po smazání indexů dává $s\!-\!b\!-\!t$.