SP v DAG v O(V+E)
Bellman-Ford [L2.12] platí za neznalost pořadí $n-1$ průchody přes všechny hrany; Dijkstra [L2.4] si dobré pořadí počítá za běhu výběrem minima — ale jen pro $c \ge 0$. Z úlohy [L2.3] T01 přitom víme, že při šťastném pořadí hran stačil Bellman-Fordovi jediný průchod. Dnešní otázka: kdy takové pořadí dostaneme zadarmo, předem a bez podmínky $c \ge 0$?
Acyklický graf = pořadí zadarmo
Zkus sám: jaké pořadí hran zaručí, že Bellman-Fordovi stačí jediný průchod?
Z intuice „$k$-tého průchodu“ [L2.12]: značka $l(w)$ je správně, jakmile byly hrany nejkratší cesty $s \to \cdots \to w$ relaxovány v pořadí podél cesty. Jediný průchod tedy stačí, když seznam hran projde každou nejkratší cestu „po proudu“ — tj. když existuje seřazení vrcholů takové, že každá hrana vede jen „doleva → doprava“, a hrany relaxujeme po vrcholech zleva doprava.
Kdy takové seřazení existuje? Přesně tehdy, když graf nemá orientovaný cyklus — na cyklu by musel být nějaký vrchol „před sebou samým“ [L0.4]. Tomu seřazení se říká topologické uspořádání a graf, který ho má, je DAG.
Definition: A topological order of $G$ is an order of the vertices $V(G) = v_1, \ldots, v_n$ such that for each edge $(v_i, v_j) \in E(G)$ we have $i < j$.
Proposition: A directed graph has a topological order if and only if it is acyclic (see the proof in [3]).
Consequence: DAG vertices can be arranged on a line so that all edges go from left to right.
Observation: shortest path from $s$ to $v_i$ cannot use any node from $v_{i+1}, \ldots, v_n$, therefore we can find the shortest paths in topological order.
Pojmy DAG a topologické uspořádání známe z [L0.4] — včetně toho, jak uspořádání najít (opakovaně odeber vrchol s nulovým in-degree, jde to v lineárním čase). Tady je graf ze slidu 40 — na první pohled obyčejný digraf se zápornými hranami:
Zkus sám: najdi topologické uspořádání grafu výše. Je jednoznačné?
Postupné odebírání vrcholů s nulovým in-degree [L0.4]: na začátku je bez vstupní hrany jen $s$. Po odebrání $s$ jen $b$ (do $a$ pořád vede $b \to a$), po $b$ jen $a$, po $a$ jen $d$. Jenže do $c$ vedou hrany $(a,c)$ i $(d,c)$ a do $e$ jen $(d,e)$ — po odebrání $d$ tak současně ztratí poslední vstupní hranu jak $c$, tak $e$ (mezi $c$ a $e$ žádná hrana není). V tomhle kroku jsou tedy kandidáti dva, takže uspořádání jednoznačné není: platné je $s, b, a, d, c, e$ i $s, b, a, d, e, c$ (výsledné značky $l$, $p$ ale vyjdou stejně; obecně nejednoznačnost čekáme, viz úloha v [L0.4]).
Teď „Consequence“ ze slidu: srovnej vrcholy v tomhle pořadí na přímku a všechny hrany potečou zleva doprava — uvidíš to na vizualizaci běhu níže.
Zkus sám: proč nejkratší cesta z $s = v_1$ do $v_i$ nemůže použít žádný z vrcholů $v_{i+1}, \ldots, v_n$?
Všechny hrany vedou v topologickém pořadí „doprava“. Kdyby cesta do $v_i$ prošla nějakým $v_j$ s $j > i$, musela by se z $v_j$ vrátit „doleva“ do $v_i$ — a žádná hrana doleva nevede. To je celé „Observation“ — a přesně ono dovolí počítat značky po vrcholech zleva doprava: ve chvíli, kdy je na řadě $v_i$, jsou už všichni možní předchůdci hotoví.
Algoritmus: jeden průchod v topologickém pořadí
Slide 41 to říká přímo: „May be seen as simplified version of Bellman-Ford algorithm.“ Místo $n-1$ průchodů přes všechny hrany [L2.12] jediný průchod po vrcholech — u vrcholu $v_i$ zrelaxuj [L2.3] všechny jeho vstupní hrany:
Input: directed acyclic graph $G$ with topologically ordered vertices $v_1, \ldots, v_n$, weights $c : E(G) \to \mathbb{R}$.
Output: vectors $l$ and $p$. For all $i = 1 \ldots n$, $l(v_i)$ is the length of the shortest path from $v_1$ and $p(v_i)$ is the last but one node. If $v_i$ is not reachable from $v_1$, then $l(v_i) = \infty$ and $p(v_i)$ is undefined.
l(v_1) := 0; l(v_i) := ∞ for i = 2 ... n;
for i := 2 to n do
for every edge of graph (v_j, v_i) ∈ E(G) do
if l(v_i) > l(v_j) + c(v_j, v_i) then
l(v_i) := l(v_j) + c(v_j, v_i); p(v_i) := v_j;
end
end
endCorrectness: induction on $i$ and observation on previous slide. — Time complexity $\mathcal{O}(|V| + |E|)$.
Zkus sám: porovnej vnitřní smyčku s Bellman-Fordem [L2.12]. Co je stejné a co se změnilo?
Relaxační if je znak po znaku stejný — společné jádro všech SP algoritmů [L2.3]. Změnilo se které hrany a kdy: Bellman-Ford bere v každém průchodu všechny hrany grafu, tady se u vrcholu $v_i$ berou jen jeho vstupní hrany $(v_j, v_i)$ — a protože vstupní hrany jednotlivých vrcholů dohromady dají každou hranu grafu právě jednou, celý běh relaxuje každou hranu přesně jednou.
A proč to stačí? Když je na řadě $v_i$, jsou značky všech $v_j$ s $j < i$ už finální (indukce) a nejkratší cesta do $v_i$ jiné předchůdce mít nemůže (Observation). Vnitřní smyčka tedy vyhodnotí Bellmanovu rovnici [L2.2] pro $v_i$ s definitivními hodnotami — $l(v_i)$ je po svém kroku hotové a už se nikdy nezmění.
Běh na grafu ze slidu 40 — vrcholy srovnané na přímce v topologickém pořadí $s, b, a, d, c, e$, hrany jdou jen zleva doprava:
Zkus sám: v kroku $i = 3$ vyhrála záporná hrana $(b,a)$ nad přímou hranou $(s,a)$. Proč to tady — na rozdíl od Dijkstry [L2.4] — nemůže nic rozbít?
Dijkstra se na záporné hraně spálila, protože vrchol uzavřela dřív, než k němu dorazila levnější (záporná) oklika — její pořadí „podle nejmenší značky“ je správné jen pro $c \ge 0$. Tady ale pořadí neurčují značky, nýbrž topologie: $a$ přijde na řadu až po $s$ i $b$, takže oklika přes $b$ je v tu chvíli už spočítaná — ať jsou váhy jakékoliv, klidně záporné. A záporný cyklus, jediný skutečný zabiják nejkratších cest [L2.1], v DAGu být nemůže — DAG nemá vůbec žádný cyklus.
Složitost a srovnání
Zkus sám: spočítej práci algoritmu a zdůvodni $\mathcal{O}(|V| + |E|)$.
Inicializace projde $n$ vrcholů → $\mathcal{O}(|V|)$. Hlavní smyčka navštíví každý vrchol jednou a každou hranu zrelaxuje právě jednou (hrana $(v_j, v_i)$ se objeví jen v kroku svého koncového vrcholu $v_i$) → $\mathcal{O}(|E|)$. Dohromady $\mathcal{O}(|V| + |E|)$ — lineárně ve velikosti grafu, rychleji to ani nejde (každou hranu je nutné aspoň přečíst). I topologické seřazení samotné stihneš v $\mathcal{O}(|V| + |E|)$ [L0.4], takže lineární zůstává i celek.
| Dijkstra [L2.4] | Bellman-Ford [L2.12] | SP v DAG | |
|---|---|---|---|
| předpoklad | $c \ge 0$ | bez záporného cyklu | acyklický graf (váhy $c \in \mathbb{R}$ libovolné) |
| pořadí relaxací | počítá za běhu (výběr minima) | žádné — všechny hrany $(n-1)\times$ | zadarmo z topologického uspořádání |
| každá hrana relaxována | $1\times$ | až $(n-1)\times$ | právě $1\times$ |
| složitost | $\mathcal{O}(n^2)$, resp. $\mathcal{O}(m + n \log n)$ | $\mathcal{O}(nm)$ | $\mathcal{O}(n + m)$ |
Korektnost je na slidu odbytá jednou větou („induction on $i$ and observation“) — a víc opravdu netřeba: indukční krok jsme si rozmysleli v try otázce výše. Na rozdíl od důkazů Dijkstry a Bellman-Forda (kapitola K3, žebříček ústních důkazů) se tady u zkoušky čeká právě tahle krátká úvaha.
Bonus zadarmo: nejdelší cesty
Zkus sám: jak stejným algoritmem najít v DAGu nejdelší cestu z $v_1$?
Dvě rovnocenné cesty: (i) vynásob všechny váhy $-1$ a pusť algoritmus beze změny — graf zůstal DAG a záporné váhy mu nevadí; nejkratší cesta v $-c$ je nejdelší v $c$. (ii) Přepiš algoritmus přímo na maximum: inicializuj $l(v_i) := -\infty$ a otoč test na $l(v_i) < l(v_j) + c(v_j, v_i)$.
V obecném grafu je nejdelší (prostá) cesta NP-těžká (souvisí s hamiltonovskou cestou — podrobně v lekci [L2.17]); povolením opakování vrcholů by se navíc přes kladné cykly délka nabalovala donekonečna. V DAGu žádný cyklus není, a tak je nejdelší cesta stejně snadná jako nejkratší. Přesně to jsme už použili u investic pana Dow Jonese [L2.9]: maximalizace zhodnocení byla nejdelší cesta v DAGu let.
Pozor: tři polopravdy kolem DAG-SP- „Prostě projdu vrcholy, jak jsou očíslované v zadání.“ Vstup algoritmu chce vrcholy už topologicky seřazené — seřazení je součást práce (taky $\mathcal{O}(|V|+|E|)$, [L0.4]). Na písemce nejdřív najdi/zdůvodni topologické pořadí (klidně graf překresli na přímku), pak teprve relaxuj.
- „Funguje to i s pár cykly, když nejsou záporné.“ Nefunguje — s jediným orientovaným cyklem topologické uspořádání vůbec neexistuje (Proposition) a algoritmus nelze ani spustit. Pak je na řadě Bellman-Ford [L2.12] (či Dijkstra [L2.4] pro $c \ge 0$).
- „Nejdelší cesta se najde snadno.“ Jen v DAGu! V obecném grafu s kladnými vahami je to NP-těžký problém (lekce [L2.17]); trik ×$(-1)$ tam vyrobí záporné cykly. Pro all-pairs variantu nejdelších cest viz Floyd [L2.14].
Key takeaways — L2.13- SP v DAG: topologicky seřaď vrcholy [L0.4] a v tomto pořadí u každého vrcholu zrelaxuj [L2.3] jeho vstupní hrany — jeden průchod, každá hrana právě jednou; značka $l(v_i)$ je po svém kroku finální (nejkratší cesta do $v_i$ nemůže použít pozdější vrcholy).
- Lineární čas $\mathcal{O}(|V| + |E|)$ včetně topologického seřazení; záporné hrany nevadí — pořadí dává topologie, ne značky, a záporný cyklus v DAGu neexistuje.
- Funguje i pro nejdelší cesty (váhy ×$(-1)$, nebo $-\infty$ + otočený test) — v DAGu snadné, v obecném grafu NP-těžké [L2.17].
- Je to „zjednodušený Bellman-Ford“ [L2.12]: topologické pořadí nahradí $n-1$ průchodů jediným. (Téma ústní.)
Definition: A topological order of $G$ is an order of the vertices $V(G) = v_1, \ldots, v_n$ such that for each edge $(v_i, v_j) \in E(G)$ we have $i < j$.
Proposition: A directed graph has a topological order if and only if it is acyclic.
Consequence: DAG vertices can be arranged on a line so that all edges go from left to right.
Observation: shortest path from $s$ to $v_i$ cannot use any node from $v_{i+1}, \ldots, v_n$, therefore we can find the shortest paths in topological order.
Algorithm for DAGs may be seen as simplified version of Bellman-Ford algorithm.
Input: directed acyclic graph $G$ with topologically ordered vertices $v_1, \ldots, v_n$, weights $c : E(G) \to \mathbb{R}$.
Output: vectors $l$ and $p$. For all $i = 1 \ldots n$, $l(v_i)$ is the length of the shortest path from $v_1$ and $p(v_i)$ is the last but one node. If $v_i$ is not reachable from $v_1$, then $l(v_i) = \infty$ and $p(v_i)$ is undefined.
Study task: compute shortest paths in a DAG by processing vertices in topological order.
(Instance for the run — own addition, the bank gives no concrete graph: the graph below, source node $A$. First find a topological order, then compute $l$ and $p$.)
a) Co je v zadání?
Studijní úloha ze slidů: na DAGu o $n = 6$ vrcholech spočítat nejkratší cesty z $A$ jediným průchodem v topologickém pořadí. Pozor — vrcholy v obrázku nejsou srovnané na přímce: první krok je topologické uspořádání najít. V grafu jsou záporné hrany a jeden vrchol, do kterého z $A$ nevede nic.
b) Co k tomu budeme potřebovat?
- Tato lekce — průchod v topologickém pořadí, finálnost značek, $\mathcal{O}(|V|+|E|)$.
- [L0.4] DAG a topologické uspořádání — jak uspořádání najít (odebírání vrcholů s nulovým in-degree).
- [L2.3] Relaxace hrany — relaxační krok, vektory $l$ a $p$.
c) Jak nad úlohou uvažovat?
Nejdřív topologie: opakovaně hledej vrcholy bez nezpracované vstupní hrany (může jich být víc → uspořádání nemusí být jednoznačné, vyber libovolné platné). Pak veď tabulku $l$ a $p$ a zpracovávej vrcholy zleva doprava: u každého projdi jen jeho vstupní hrany a vezmi minimum z $l(\text{předchůdce}) + c$. Hodnoty předchůdců už jsou finální, takže se k hotovému vrcholu nikdy nevracíš. Nedosažitelný vrchol prostě zůstane na $\infty$ — a dej pozor, co jeho $\infty$ udělá (neudělá) s hranami, které z něj vedou.
d) Úplné řešení (vlastní — banka úlohu neřeší)
Topologické uspořádání. Nulový in-degree mají na startu $A$ i $E$ — uspořádání tedy není jednoznačné (srov. [L0.4]). Zvolme $A, C, B, D, E, F$: ověř, že každá hrana vede doprava — $(A,C), (A,B), (C,B), (C,D), (B,D), (B,F), (D,F), (E,F)$ ✓. (Stejně dobré je např. $E, A, C, B, D, F$; výsledné $l$, $p$ vyjdou totožně.)
Průchod (u každého vrcholu minimum přes vstupní hrany, hodnoty předchůdců už finální):
- $i=2$, vrchol $C$: vstupní $(A,C)$: $l(C) = 0 + 2 = 2$, $p(C) = A$.
- $i=3$, vrchol $B$: $(A,B)$: $0 + 5 = 5$; $(C,B)$: $2 + (-3) = -1$ → $l(B) = -1$, $p(B) = C$ (záporná hrana v klidu vyhrála — oklika přes $C$ je levnější než přímá hrana).
- $i=4$, vrchol $D$: $(C,D)$: $2 + 4 = 6$; $(B,D)$: $-1 + 1 = 0$ → $l(D) = 0$, $p(D) = B$.
- $i=5$, vrchol $E$: žádná vstupní hrana → $l(E) = \infty$, $p(E)$ nedefinováno (přesně dle výstupní specifikace).
- $i=6$, vrchol $F$: $(B,F)$: $-1 + 4 = 3$; $(D,F)$: $0 + 2 = 2$; $(E,F)$: $\infty + 1$ nic nepodleze → $l(F) = 2$, $p(F) = D$.
| $A$ | $C$ | $B$ | $D$ | $E$ | $F$ | |
|---|---|---|---|---|---|---|
| $l$ | $0$ | $2$ | $-1$ | $0$ | $\infty$ | $2$ |
| $p$ | $-$ | $A$ | $C$ | $B$ | $-$ | $D$ |
Strom nejkratších cest: $A \to C$, $C \to B$, $B \to D$, $D \to F$; např. do $F$ vede $A \to C \to B \to D \to F$ s délkou $2 - 3 + 1 + 2 = 2$. Každá z $8$ hran byla relaxována právě jednou → $\mathcal{O}(|V| + |E|)$.
Krokovaný běh řešení T01 (pozor, spoiler — nejdřív si projdi tabulku sám na papír):