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

Dijkstrův algoritmus (běh)

Jedna nová věc Dijkstrova strategie pořadí relaxací: opakovaně vyber neuzavřený vrchol s nejmenší značkou $l$, uzavři ho a relaxuj jeho odchozí hrany. Pro nezáporné váhy je takto uzavřená značka rovnou definitivní — Dijkstra je label-setting algoritmus.

Prerekvizity: [L2.3] Relaxace hrany. Tam jsme viděli, že všechny algoritmy kapitoly skládají týž krok — relaxaci — a liší se jen strategií pořadí. Dnes první a nejslavnější strategie: Dijkstra [1959].

Jakou strategii pořadí zvolit?

Z úlohy T01 v [L2.3] víš, že dobré pořadí relaxací ušetří celé průchody. Ideál by byl relaxovat odchozí hrany každého vrcholu právě jednou — a to jde jen tehdy, když vrchol expanduju až ve chvíli, kdy už se jeho značka nikdy nezmění.

Zkus sám: váhy hran jsou nezáporné. U kterého z neuzavřených vrcholů si můžeš být jistý, že jeho aktuální značka $l(v)$ už neklesne?

U toho s nejmenší značkou $l(v) = \min_{i \notin R} l(i)$ (kde $R$ je množina už uzavřených vrcholů). Proč: kdyby do $v$ vedla ještě kratší cesta, musela by někde poprvé opustit $R$ — přes nějaký neuzavřený vrchol $k$. Jenže ten má značku $l(k) \ge l(v)$ a zbytek cesty z $k$ do $v$ jen přidává nezáporné délky. Kratší to tedy být nemůže.

Přesně tohle je Dijkstrův nápad: vrchol s nejmenší značkou smím uzavřít (prohlásit značku za definitivní) a jeho odchozí hrany relaxovat — každou jen jednou za celý běh.

(Tohle je intuice; poctivý indukční důkaz korektnosti patří do kapitoly K3 — tady v K2 nás zajímá běh a použití.)

Dijkstra Algorithm [1959] — nonnegative weights (slide 16, 1:1)

Input: digraph $G$, weights $c : E(G) \to \mathbb{R}^+_0$ and node $s \in V(G)$.
Output: Vectors $l$ and $p$. For $v \in V(G)$, $l(v)$ is the length of the shortest path from $s$ and $p(v)$ is the previous node in the path. If $v$ is unreachable from $s$, $l(v) = \infty$ and $p(v)$ is undefined.

l(s) := 0; l(v) := ∞ for v ≠ s; R := ∅;
while R ≠ V(G) do
    Find v ∈ V(G) \ R such that l(v) = min_{i ∈ V(G) \ R} l(i);
    R := R ∪ {v}  // in the first run we add vertex s
    // further calculate non-permanent value of l(w) for
    //   every node on border of R
    for w ∈ V(G) \ R such that (v, w) ∈ E(G) do
        if l(w) > l(v) + c(v, w) then
            l(w) := l(v) + c(v, w); p(w) := v;
        end
    end
end

Vnitřní if je doslova relaxace z [L2.3]. Výběru vrcholu $v$ a relaxaci jeho odchozích hran se říká expanze vrcholu $v$ — na pořadí expanze se zaměří hned další lekce [L2.5]. Množina $R$ obsahuje uzavřené (permanent) vrcholy: jejich $l$ už je výsledná vzdálenost.

Běh na příkladu

Proklikej si celý běh ze startu $s$ — sleduj, jak se vrcholy uzavírají v pořadí rostoucí značky a jak se značky na hranici $R$ ještě opravují:

Zkus sám: vrchol $b$ dostal nejdřív značku $l(b)=5$ (přímou hranou), a přesto se uzavřel s $l(b)=4$. Není to spor s tím, že Dijkstra značky „zatrvalňuje“?

Není. Trvalá je značka až okamžikem uzavření (přidání do $R$). Dokud je vrchol venku, jeho značka je obyčejný pracovní odhad z [L2.3] a smí klesat — to se stalo $b$ při expanzi $a$. Slide 16 tomu říká non-permanent value on border of R: hranice $R$ má rozpracované odhady, vnitřek $R$ hotové vzdálenosti.

Všimni si pořadí uzavírání: $s\,(0),\ a\,(2),\ b\,(4),\ c\,(5)$ — značky uzavíraných vrcholů neklesají. To je charakteristický rys Dijkstry a budeme ho potřebovat v [L2.5].

Zkus sám: co se stane, když je minimum mezi neuzavřenými vrcholy $\infty$? A kdy můžeš běh ukončit dřív, když tě zajímá jen jeden cíl $t$?

Minimum $\infty$ znamená, že do žádného zbylého vrcholu jsme zatím neviděli cestu — a protože expandované hrany vedou jen z $R$, už ani neuvidíme. Takové vrcholy jsou nedosažitelné: uzavřou se s $l(v) = \infty$ a $p(v)$ nedefinovaným, přesně podle výstupní specifikace slidu 16. (Relaxace z nich nic neudělají: $\infty + c$ nic nepodleze.)

A pokud hledáme jen cestu $s \to t$: jakmile se $t$ dostane do $R$, jeho značka je definitivní — algoritmus lze ukončit v okamžiku zařazení $t$ do $R$ (slide 21). Zbytek běhu by počítal vzdálenosti, které nepotřebujeme.

Proč „nonnegative weights“ není jen okrasa

Zkus sám: najdi co nejmenší graf se zápornou hranou (ale bez záporného cyklu!), na kterém Dijkstra vrátí špatnou vzdálenost.

Stačí tři vrcholy: $s \to a$ s váhou $1$, $s \to b$ s váhou $2$ a $b \to a$ s váhou $-2$. Skutečná nejkratší cesta do $a$ vede přes $b$ a má délku $0$. Dijkstra ale uzavře $a$ hned ve druhé iteraci se značkou $1$ — minimum mezi neuzavřenými — a tu už nikdy nepřepíše. Proklikej:

Krokovaný protipříklad (pozor, spoiler — nejdřív zkus najít vlastní graf na papír):

Pozor: Dijkstra funguje JEN pro nezáporné váhy

Celý trik „nejmenší značka = hotovo“ stojí na tom, že obejití přes jiný vrchol může délku jen přidat. Záporná hrana tenhle argument zboří — a to i bez záporného cyklu [L2.1] a přesto, že samotné relaxaci záporné váhy nevadí [L2.3]. Pokazí se strategie pořadí, ne relaxace.
Se zápornými hranami (bez záporných cyklů) je potřeba label-correcting algoritmus — Bellman-Ford [L2.12].

Label-setting vs. label-correcting, složitost

Dijkstra je tzv. label-setting algoritmus (slide 20): v každé iteraci se jedna značka $l(v)$ stane trvalou (optimální). Naproti tomu label-correcting algoritmy (např. Bellman-Ford [L2.12] nebo Floyd [L2.14]) považují všechny značky za dočasné až do úplně posledního kroku, kdy se trvalými stanou všechny najednou — přesně jak sliboval výhled v [L2.3].

Časová složitost Dijkstry je $\mathcal{O}(n^2)$, resp. $\mathcal{O}(m + n \log n)$ s prioritní frontou (datová struktura, která umí rychle vydávat minimum; $n = |V(G)|$, $m = |E(G)|$). Pro speciální grafy existují i lineární algoritmy — mj. pro DAGy, kde pořadí relaxací dostaneme zadarmo z topologického uspořádání [L2.13].

Key takeaways — L2.4

Dijkstrův běh: udržuj vektory $l$ a $p$ [L2.3]; opakovaně vyber neuzavřený vrchol s nejmenším $l$, přidej ho do $R$ (uzavři) a relaxuj jeho odchozí hrany do neuzavřených vrcholů.
Vrcholy se uzavírají v pořadí neklesajících značek; značka je trvalá od okamžiku uzavření (label-setting), na hranici $R$ je jen pracovní odhad. Nedosažitelné vrcholy skončí s $l = \infty$, $p$ nedefinované; při hledání jediného cíle $t$ lze skončit zařazením $t$ do $R$.
Funguje JEN pro nezáporné váhy — záporná hrana (i bez záporného cyklu) rozbije argument „přes dražší vrchol to kratší být nemůže“. Pak je nutný Bellman-Ford [L2.12].
Složitost $\mathcal{O}(n^2)$, resp. $\mathcal{O}(m + n \log n)$ s prioritní frontou. Důkaz korektnosti (indukce přes $R$) patří do kapitoly K3.

T01 Dijkstra — iterate on a graph of 8 nodes zdroj: testy/a4b35ko__test2_2015.md (Test 2, zadání A i B — Dijkstra na grafu o 8 uzlech, vektory l a p; konkrétní graf se v přepisu nedochoval, graf níže je vlastní rekonstrukce ve formátu zadání; požadavek na pořadí přidávání do R je doplněn nad rámec přepisu — využije se v L2.5)

Assignment (EN, formát dle test2 2015)

You are given the directed graph with 8 nodes below. Run Dijkstra's algorithm from node $1$ and create two vectors $l$ and $p$, where vector $l$ contains the lengths of the shortest paths from the starting node and vector $p$ contains the predecessor of each node. Perform 8 iterations of the algorithm and write out the vectors after each iteration. In addition, write out the order in which the nodes were added to the set $R$.

a) Co je v zadání?

Orientovaný graf s 8 vrcholy a nezápornými váhami, start ve vrcholu $1$. Máme oditerovat Dijkstru: po každé z 8 iterací (každá uzavře jeden vrchol) vypsat aktuální vektory $l$ a $p$ a nakonec uvést pořadí uzavírání. Pozor na vrchol $8$ — nevede do něj žádná hrana.

b) Co k tomu budeme potřebovat?

Tato lekce — výběr minima mezi neuzavřenými, uzavření, expanze.
[L2.3] Relaxace hrany — test s ostrou nerovností, zápis $l$ a $p$.

c) Jak nad úlohou uvažovat?

Veď si tabulku: řádek = iterace, sloupce = $l(1), \dots, l(8)$, a zvlášť si značkuj, kdo už je v $R$. V každé iteraci nejdřív vyber minimum mezi neuzavřenými (zapiš si pořadí!), pak relaxuj jen jeho odchozí hrany do neuzavřených vrcholů. Nezapomeň: při rovnosti $l(w) = l(v) + c(v,w)$ se nepřepisuje nic — test je ostrý. Hodnoty $\infty$ nech $\infty$, dokud je relaxace skutečně nesníží.

d) Úplné řešení

Init: $l = (0, \infty, \infty, \infty, \infty, \infty, \infty, \infty)$, $R = \emptyset$. Zápis $l$ vždy po dokončení iterace; změny tučně.

It 1: min je $1\,(0)$ → $R=\{1\}$. Relaxace $(1,2)$: $l(2):=\mathbf{4}$, $p(2):=1$; $(1,3)$: $l(3):=\mathbf{1}$, $p(3):=1$. → $l = (0, 4, 1, \infty, \infty, \infty, \infty, \infty)$.
It 2: min je $3\,(1)$ → uzavři $3$. $(3,5)$: $l(5):=\mathbf{3}$, $p(5):=3$; $(3,4)$: $l(4):=\mathbf{7}$, $p(4):=3$. → $l = (0, 4, 1, 7, 3, \infty, \infty, \infty)$.
It 3: min je $5\,(3 \lt 4)$ → uzavři $5$ (dřív než $2$!). $(5,6)$: $l(6):=\mathbf{7}$, $p(6):=5$. → $l = (0, 4, 1, 7, 3, 7, \infty, \infty)$.
It 4: min je $2\,(4)$ → uzavři $2$. $(2,4)$: $7 \gt 4+2 = 6$ → $l(4):=\mathbf{6}$, $p(4):=2$ (oprava odhadu na hranici $R$). → $l = (0, 4, 1, 6, 3, 7, \infty, \infty)$.
It 5: min je $4\,(6)$ → uzavři $4$. $(4,6)$: $7 \gt 6+1 = 7$? Ne — rovnost, ostrý test nepustí, $p(6)$ zůstává $5$. $(4,7)$: $l(7):=\mathbf{10}$, $p(7):=4$. → $l = (0, 4, 1, 6, 3, 7, 10, \infty)$.
It 6: min je $6\,(7)$ → uzavři $6$. $(6,7)$: $10 \gt 7+2 = 9$ → $l(7):=\mathbf{9}$, $p(7):=6$ — druhá oprava. → $l = (0, 4, 1, 6, 3, 7, 9, \infty)$.
It 7: min je $7\,(9)$ → uzavři $7$. Žádné odchozí hrany. → $l$ beze změny.
It 8: zbývá jen $8$ s $l(8) = \infty$ → uzavři $8$. Vrchol je z $1$ nedosažitelný: $l(8) = \infty$, $p(8)$ nedefinované (přesně dle výstupní specifikace slidu 16). $R = V(G)$, konec.

Výsledné vektory:

$$l = (0,\, 4,\, 1,\, 6,\, 3,\, 7,\, 9,\, \infty), \qquad p = (-,\, 1,\, 1,\, 2,\, 3,\, 5,\, 6,\, -).$$

Pořadí přidávání do $R$: $1, 3, 5, 2, 4, 6, 7, 8$ — značky $0, 1, 3, 4, 6, 7, 9, \infty$ neklesají ✓. Kontrola cestou: couváním ze $7$ po $p$: $p(7)=6$, $p(6)=5$, $p(5)=3$, $p(3)=1$ → nejkratší cesta $1 \to 3 \to 5 \to 6 \to 7$ délky $1+2+4+2 = 9 = l(7)$ ✓.

Krokovaná verze řešení (pozor, spoiler — nejdřív si to zkus na papír):

Lekci mám hotovou