Nejdelší cesta: kdy je těžká a kdy snadná
S nejdelší cestou jsme se v K2 už třikrát potkali: maximalizace zhodnocení pana Dow Jonese byla nejdelší cesta v DAGu [L2.9], jednoprůchodový algoritmus pro DAG ji zvládl trikem $\times(-1)$ [L2.13] a totéž jsme udělali u all-pairs Floyda [L2.14]. Pokaždé jsme ale přibalili varování „v obecném grafu je to NP-těžké — podrobně v L2.17“. Dnes ten dluh splatíme: nakreslíme si přesnou hranici mezi snadnými a těžkými instancemi.
Trik ×(−1) a jeho tichá podmínka
Slide 5 přednášky říká (EN 1:1): „The longest path can be transformed to the shortest path while reversing the sign of weights. Thus, we search for the minimum instead of the maximum.“ Otočení znamének (násobení $-1$) převádí maximalizaci $c(P)$ na minimalizaci $-c(P)$; na rozdíl od kladného skálování [L2.15] (které zachovává nejkratší cestu jen pro $k > 0$) ale otočí i pořadí, tedy mění max na min.
Zkus sám: otočení znamének je mechanické a jde provést vždy. Proč tedy nejdelší cesta není vždy stejně snadná jako nejkratší?
Protože transformace sice vždy proběhne, ale výsledná instance nejkratší cesty nemusí splňovat vstupní podmínky algoritmů: žádné záporné cykly [L2.1] (a pro Dijkstru dokonce žádné záporné váhy [L2.4]). A přesně tady je háček: $\times(-1)$ překlopí znaménko každého cyklu. Kladný cyklus v původním grafu = záporný cyklus v otočeném. Otázka „kdy je nejdelší cesta snadná“ je tedy otázka „kdy původní graf nemá kladný cyklus“.
Podívej se na konkrétní graf — kladné váhy a cyklus $a \rightleftarrows b$ o váze $1 + 1 = +2$:
Pro nejdelší cestu je kladný cyklus přesně to, co byl záporný cyklus pro nejkratší [L2.1] — zrcadlově. Tam délka sledu kolem cyklu padala k $-\infty$; tady poroste nade všechny meze:
Zkus sám: otoč v grafu nahoře všechny váhy ($\times(-1)$). Co dostaneš a co na to algoritmy z téhle kapitoly?
Všechny váhy budou záporné a cyklus $a \rightleftarrows b$ bude mít váhu $-2$ — záporný cyklus. Z lekce [L2.1] víme, co to znamená: nejkratší sled neexistuje, algoritmy ztotožňující sled s cestou (Dijkstra, Bellman-Ford, Floyd) nelze použít a hledání nejkratší cesty je v takové instanci NP-těžké. Bellman-Ford záporný cyklus aspoň detekuje [L2.12] — ale vyřešit úlohu neumí.
Proč rovnou NP-těžká: souvislost s Hamiltonovskou cestou
„Algoritmy z K2 selžou“ ještě neznamená „neexistuje žádný chytřejší algoritmus“. U nejdelší cesty s kladnými vahami ale platí silnější tvrzení — a důvod si můžeš odvodit sám:
Zkus sám: polož všem hranám grafu $G$ s $n$ vrcholy váhu $1$ (kladnou!). Jak dlouhá může nejdelší cesta nanejvýš být — a kdy se té meze dosáhne?
Cesta neopakuje vrcholy, takže má nejvýš $n - 1$ hran; s jednotkovými vahami je tedy její délka nejvýš $n - 1$. Délky $n - 1$ dosáhne právě cesta procházející všemi vrcholy — tedy Hamiltonovská cesta (Hamiltonian path). Kdybychom uměli nejdelší cestu počítat polynomiálně, uměli bychom polynomiálně rozhodnout i existenci Hamiltonovské cesty: stačí se zeptat, zda nejdelší cesta má délku $n-1$. Existence Hamiltonovské cesty je ale NP-těžký problém — takže NP-těžká je i nejdelší cesta s kladnými vahami v obecném grafu.
Je to stejný druh argumentu jako redukce z Hamiltonovské kružnice na nejkratší cestu se záporným cyklem, kterou jsme si načrtli v [L2.1] (slide 12). Formální redukce a pojmy NP-úplnosti patří do teorie (kapitola K3, [L3.3] Hamiltonovská kružnice a NP-úplnost) — na písemku stačí věta: „nejdelší cesta s kladnými vahami v obecném grafu je NP-těžká, protože by rozhodovala existenci Hamiltonovské cesty“.
Kdy je nejdelší cesta snadná
Zkus sám: teď obráceně — všechny váhy v grafu jsou záporné. Co udělá $\times(-1)$ a kdo to dořeší?
Po otočení jsou všechny váhy kladné — nejpohodlnější možná instance nejkratší cesty. Žádné záporné cykly, žádné záporné hrany: stačí Dijkstra [L2.4]. Nejdelší cesta v původním grafu je pak nalezená nejkratší cesta s délkou $\times(-1)$. Zrcadlo platí dokonale: u nejkratší cesty jsou „bezpečné“ nezáporné váhy, u nejdelší záporné.
Běh na otočeném grafu (váhy už $\times(-1)$):
Zkus sám: a co DAG [L0.4] — klidně s kladnými vahami? Kde se tam schová kladný cyklus?
Nikde — DAG žádný cyklus nemá, takže nemá ani kladný. Po $\times(-1)$ vzniknou sice záporné váhy, ale žádný záporný cyklus, a v topologickém pořadí to jeden průchod spočítá v $O(|V| + |E|)$ [L2.13] (znaménko vah je tomu algoritmu úplně jedno). Proto byla maximalizace zhodnocení pana Dow Jonese [L2.9] — nejdelší cesta v DAGu let — snadná úloha, žádný paradox.
Shrnutí celé hranice v jedné tabulce. Společný jmenovatel snadných řádků: po $\times(-1)$ nevznikne záporný cyklus — tedy původní graf nesmí obsahovat kladný cyklus (to je odpověď na otázku ze slidu 11, viz úloha T01):
| Instance nejdelší cesty | Po $\times(-1)$ | Složitost | Algoritmus |
|---|---|---|---|
| kladné váhy, obecný graf s cyklem | záporné cykly | NP-těžká | — (rozhodovala by Hamiltonovskou cestu) |
| všechny váhy záporné (libovolný graf) | kladné váhy | snadná | Dijkstra [L2.4] |
| libovolné váhy, žádný kladný cyklus | žádný záporný cyklus | snadná | Bellman-Ford [L2.12] |
| DAG, libovolné váhy | DAG (beze změny struktury) | snadná, $O(|V|+|E|)$ | jeden průchod [L2.13]; all-pairs Floyd [L2.14] |
Pozor: nebezpečné polopravdy- „Nejdelší cesta se vyřeší otočením znamének — vždy.“ NE. Transformace proběhne vždy, ale řešitelná je výsledná instance jen tehdy, když nevznikl záporný cyklus — tj. když původní graf nemá kladný cyklus. Jinak je úloha NP-těžká.
- „Kladné váhy = bezpečí.“ U nejkratší cesty ano — u nejdelší je to přesně naopak: kladné váhy dělají z každého cyklu kladný cyklus. Bezpečné jsou tu váhy záporné.
- „Nejdelší cesta je NP-těžká, takže Dow Jones / DAG úlohy jsou těžké.“ NE — NP-těžkost platí pro obecné grafy s kladnými cykly. V DAGu je nejdelší cesta vždy snadná [L2.13].
Key takeaways — L2.17- Nejdelší cesta = nejkratší cesta po $\times(-1)$ — ale transformace překlopí znaménko každého cyklu: kladný cyklus v původním grafu = záporný cyklus v otočeném.
- Kladné váhy v obecném grafu → NP-těžká: s jednotkovými vahami má nejdelší cesta délku $n-1$ právě tehdy, když existuje Hamiltonovská cesta — zrcadlo NP-těžkosti nejkratší cesty se záporným cyklem [L2.1].
- Všechny váhy záporné → snadné: $\times(-1)$ dá kladné váhy a stačí Dijkstra [L2.4]; obecněji stačí, aby graf neměl kladný cyklus (pak po otočení není záporný cyklus → Bellman-Ford [L2.12]).
- DAG → vždy snadné: žádné cykly = žádné kladné cykly; jeden topologický průchod v $O(|V|+|E|)$ [L2.13] bez ohledu na znaménka vah.
- Zkoušková mantra: u výroku o nejdelší cestě se vždy ptej „má graf kladný cyklus?“ — to je jediná hranice mezi snadným a NP-těžkým.
What the graph can not contain, when interested in the longest path?
a) Co je v zadání?
Krátká teoretická otázka navazující na fakta ze slidu 11: rychlost algoritmů pro nejkratší cesty stojí na tom, že nerozlišují cestu od sledu — a záporný cyklus tuhle ekvivalenci ničí. Otázka chce zrcadlový závěr pro nejdelší cestu: jaká struktura v grafu ji rozbije?
b) Co k tomu budeme potřebovat?
- Tato lekce — kladný cyklus jako zrcadlo záporného.
- [L2.1] Záporné váhy ano, záporné cykly ne — proč záporný cyklus dělá nejkratší cestu NP-těžkou.
c) Jak nad úlohou uvažovat?
Převeď nejdelší cestu na nejkratší trikem $\times(-1)$ a zeptej se, co nesmí obsahovat transformovaný graf. Pak podmínku přelož zpět do řeči původního grafu. Pro plnou odpověď přidej, proč je ta struktura zhoubná (sled vs. cesta).
d) Úplné řešení (vlastní)
Graf nesmí obsahovat cyklus kladné váhy (kladný cyklus).
Zdůvodnění. Nejdelší cesta se hledá jako nejkratší cesta po otočení znamének vah ($\times(-1)$). Algoritmy pro nejkratší cesty vyžadují graf bez záporných cyklů [L2.1] — a záporný cyklus v otočeném grafu je přesně kladný cyklus v původním. Přímo v řeči nejdelší cesty: kolem kladného cyklu lze sled prodlužovat donekonečna (každý oběh přidá kladnou váhu), takže nejdelší sled neexistuje a algoritmy ztotožňující sled s cestou selžou; hlídat opakování vrcholů explicitně znamená NP-těžkou úlohu (s jednotkovými vahami by rozhodovala existenci Hamiltonovské cesty). Cykly záporné (a nulové) váhy naopak nevadí — po otočení jsou kladné (nulové). $\blacksquare$
Poznámka k ústní: srovnej se zrcadlovým tvrzením pro nejkratší cestu („nesmí obsahovat záporný cyklus“) — jde o tutéž větu, jen s otočeným znaménkem.
Decide whether the following statement holds. If it does, prove it; if it does not, give a counterexample: “The longest path between two nodes in a graph with positive edge weights can always be found by multiplying all edge weights by $-1$ and running Dijkstra's algorithm.”
a) Co je v zadání?
Výrok kombinuje dva kroky: transformaci $\times(-1)$ (sama o sobě korektní převod max $\to$ min) a volbu algoritmu (Dijkstra). Rozhodni, zda dvojice funguje vždy — pozor, „vždy“ vyvrátí jediný protipříklad.
b) Co k tomu budeme potřebovat?
- Tato lekce — co $\times(-1)$ udělá se znaménky vah a cyklů.
- [L2.4] Dijkstrův algoritmus (běh) — vstupní podmínka nezáporných vah a protipříklad, proč se záporné hrany rozbije.
- [L2.12] Bellman-Ford — kdo zvládne záporné váhy bez záporných cyklů.
c) Jak nad úlohou uvažovat?
Nejdřív zkontroluj vstupní podmínky: jaké váhy dostane Dijkstra po otočení kladných vah? Pak hledej co nejmenší graf, kde Dijkstra na otočených vahách uzavře cíl předčasně. Nakonec si rozmysli, jestli výrok jde „zachránit“ výměnou algoritmu — a kde ani to nepomůže.
d) Úplné řešení (vlastní)
Výrok NEPLATÍ.
Protipříklad. Vrcholy $\{s, a, t\}$, kladné váhy $c(s,a) = 1$, $c(a,t) = 2$, $c(s,t) = 2$. Nejdelší $s \to t$ cesta je $s \to a \to t$ s délkou $3$. Po $\times(-1)$ jsou váhy $-1, -2, -2$ — všechny záporné, čímž padá vstupní podmínka Dijkstry [L2.4]. A skutečně: Dijkstra po expanzi $s$ má $l(a) = -1$, $l(t) = -2$, jako minimum vybere a uzavře $t$ se značkou $-2$; hranu $(a,t)$ už nikdy netestuje (vnitřní smyčka relaxuje jen vrcholy mimo $R$). Vrátí tedy „nejkratší cestu“ $s \to t$ délky $-2$, tj. nejdelší cestu délky $2$ — ale správně je $3$. (Graf níže, pod řešením.) $\blacksquare$
Proč to nejde zachránit jen tak: protipříklad je dokonce DAG — tam stačí vyměnit algoritmus: Bellman-Ford [L2.12] (záporné váhy bez záporných cyklů zvládá) nebo jeden topologický průchod [L2.13] vrátí správně $-3$, tedy nejdelší cestu $3$. Jakmile ale graf s kladnými vahami obsahuje cyklus, je po otočení záporný, selže i Bellman-Ford (cyklus jen detekuje) a žádná jednoduchá náhrada neexistuje — úloha je NP-těžká (tato lekce, T01).
Oprava výroku (hodí se k ústní): „…can be found by multiplying weights by $-1$ and running Dijkstra“ platí, jsou-li všechny původní váhy záporné (po otočení kladné); pro kladné váhy platí jen v DAGu, a to s algoritmem pro záporné váhy místo Dijkstry.