13-dijkstra/13-dijkstra.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{13}{Nejkrat¹í cesty: relaxaèní metody}{}
   4
   5 \def\ppsp{1-1}
   6 \def\sssp{1-$n$}
   7 \def\apsp{$n$-$n$}
   8
   9 Problém hledání nejkrat¹í cesty v~(obvykle ohodnoceném orientovaném) grafu
  10 provází teorii grafových algoritmù od~samých poèátkù. Základní algoritmy
  11 pro hledání cest jsou nedílnou souèástí základních kursù programování
  12 a algoritmù, my se budeme vìnovat zejména rùzným jejich vylep¹ením.
  13
  14 Mìjme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena
  15 {\I délkou} $\ell(e)$, co¾ je nìjaké reálné èíslo. Pro libovolnou
  16 posloupnost hran~$P$ (speciálnì tedy pro sled nebo cestu) definujeme
  17 její délku $\ell(P)$ jako souèet délek v¹ech hran posloupnosti.
  18 Za {\I vzdálenost} $d(u,v)$ dvou vrcholù prohlásíme nejmen¹í mo¾nou
  19 délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho,
  20 minimum v¾dy existuje). Pokud z~$u$ do~$v$ ¾ádná cesta nevede, polo¾íme
  21 $d(u,v) := \infty$.
  22
  23 Obvykle se studují následující tøi varianty problému:
  24
  25 \itemize\ibull
  26 \:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkrat¹í
  27   ze~v¹ech cest z~daného vrcholu~$u$ do~daného vrcholu~$v$.
  28 \:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
  29   nalézt nejkrat¹í cesty do~v¹ech ostatních vrcholù.
  30 \:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkrat¹í cesty
  31   mezi v¹emi dvojicemi vrcholù.
  32 \endlist
  33
  34 Pøekvapivì, tak obecnì, jak jsme si uvedené problémy definovali, je neumíme
  35 øe¹it v~polynomiálním èase: pro grafy, které mohou obsahovat hrany záporných
  36 délek bez jakýchkoliv omezení, je toti¾ hledání nejkrat¹í cesty NP-tì¾ké
  37 (lze na~nìj snadno pøevést existence hamiltonovské cesty). V¹echny známé
  38 polynomiální algoritmy toti¾ místo nejkrat¹í cesty hledají nejkrat¹í sled
  39 -- nekontrolují toti¾ nijak, zda cesta neprojde jedním vrcholem vícekrát.
  40
  41 Na¹tìstí pro nás je to v~grafech bez cyklù záporné délky toté¾: pokud se
  42 v~nalezeném sledu vyskytne cyklus, mù¾eme jej \uv{vystøihnout} a tím získat
  43 sled, který není del¹í, a~který má ménì hran. Ka¾dý nejkrat¹í sled tedy
  44 mù¾eme upravit na~stejnì dlouhou cestu.
  45 V~grafech bez záporných cyklù je tedy jedno, zda hledáme sled nebo cestu;
  46 naopak vyskytne-li se záporný cyklus dosa¾itelný z~poèáteèního vrcholu,
  47 nejkrat¹í sled ani neexistuje.
  48
  49 Navíc se nám bude hodit, ¾e ka¾dý prefix nejkrat¹í cesty je opìt nejkrat¹í
  50 cesta. Jinými slovy pokud nìkterá z~nejkrat¹ích cest z~$u$ do~$v$ vede
  51 pøes nìjaký vrchol~$w$, pak její èást z~$u$ do~$w$ je jednou z~nejkrat¹ích
  52 cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í
  53 cestu.)
  54
  55 Díky této vlastnosti mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom
  56 nejkrat¹ích cest}~${\cal T}(u)$. To je strom definovaný na~vrcholech zadaného
  57 grafu~$G$, zakoøenìný v~$u$ a orientovaný smìrem od~koøene, takový, ¾e pro ka¾dý
  58 vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou z~nejkrat¹ích
  59 cest z~$u$ do~$v$ v~grafy~$G$.
  60
  61 \>{\bo Pozorování:} Strom nejkrat¹ích cest v¾dy existuje.
  62
  63 \proof
  64 Nech» $u=v_1,\ldots,v_n$ jsou v¹echny vrcholy grafu~$G$. Indukcí budeme
  65 dokazovat, ¾e pro ka¾dé~$i$ existuje strom~${\cal T}_i$, v~nìm¾ se nacházejí nejkrat¹í
  66 cesty z~vrcholu~$u$ do vrcholù $v_1,\ldots,v_i$. Pro $i=1$ staèí uvá¾it
  67 strom obsahující pouze vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
  68 strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkrat¹í cestu z~$u$ do~$v_i$
  69 a oznaèíme~$z$ poslední vrchol na~této cestì, který se je¹tì vyskytuje v~${\cal T}_{i-1}$.
  70 Úsek nejkrat¹í cesty od~$z$ do~$v_i$ pak pøidáme do~${\cal T}_{i-1}$
  71 a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
  72 nejkrat¹í.
  73 \qed
  74
  75 Zbývá se dohodnout, v~jakém tvaru mají na¹e algoritmy vydávat výsledek.
  76 U~problémù typu \ppsp{} je nejjednodu¹¹í vypsat celou cestu, u~\sssp{} mù¾eme jako výstup
  77 vydat strom nejkrat¹ích cest z~daného poèátku (v¹imnìte si, ¾e staèí
  78 uvést pøedchùdce ka¾dého vrcholu), u~\apsp{} vydáme strom nejkrat¹ích cest
  79 pro ka¾dý ze~zdrojových vrcholù.
  80
  81 Èasto se ov¹em uká¾e, ¾e podstatná èást problému se skrývá v~samotném
  82 výpoètu vzdáleností a sestrojení pøedchùdcù je triviálním roz¹íøením algoritmu.
  83 Budeme tedy obvykle jen poèítat vzdálenosti a samotnou rekonstrukci cest
  84 ponecháme ètenáøi jako snadné cvièení.
  85
  86 \h{Relaxaèní algoritmus}
  87
  88 Zaènìme problémem \sssp{} a oznaème~$u$ výchozí vrchol. Vìt¹ina známých
  89 algoritmù funguje tak, ¾e pro ka¾dý vrchol~$v$ udr¾ují ohodnocení $h(v)$,
  90 které v~ka¾dém okam¾iku odpovídá délce nìjakého sledu z~$u$ do~$v$. Postupnì
  91 toto ohodnocení upravují, a¾ se z~nìj stane vzdálenost $d(u,v)$ a algoritmus
  92 se mù¾e zastavit.
  93
  94 Vhodnou operací pro vylep¹ování ohodnocení je takzvaná {\I relaxace.}
  95 Vybereme si nìjaký vrchol~$v$ a pro v¹echny jeho sousedy~$w$ spoèítáme
  96 $h(v) + \ell(v,w)$, tedy délku sledu, který vznikne roz¹íøením aktuálního
  97 sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota men¹í ne¾~$h(w)$,
  98 tak jí $h(w)$ pøepí¹eme.
  99
 100 Relaxace tedy zachovává to, ¾e ohodnocení odpovídá délkám nìjakých sledù,
 101 a~souèasnì toto ohodnocení mù¾e zlep¹ovat. Budeme se tedy sna¾it nìjaké
 102 poèáteèní ohodnocení (nabízí se $h(u)=0$, $h(v)=\infty$ pro $v\ne u$)
 103 postupnými relaxacemi pøetvoøit na~ohodnocení vzdálenostmi.
 104
 105 Abychom zabránili opakovaným relaxacím tého¾ vrcholu, které nic nezmìní,
 106 budeme rozli¹ovat tøi stavy vrcholù: {\I nevidìn} (je¹tì jsme ho nenav¹tívili),
 107 {\I otevøen} (zmìnilo se ohodnocení, èasem chceme relaxovat) a {\I uzavøen}
 108 (u¾ jsme relaxovali a není potøeba znovu).
 109
 110 Ná¹ algoritmus bude fungovat následovnì:
 111
 112 \algo
 113 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
 114 \:$\<stav>(*)\leftarrow\<nevidìn>$, $\<stav>(u)\leftarrow\<otevøen>$.
 115 \:Dokud existují otevøené vrcholy, opakujeme:
 116 \::$v\leftarrow\hbox{libovolný otevøený vrchol}$.
 117 \::$\<stav>(v)\leftarrow\<uzavøen>$.
 118 \::Relaxujeme~$v$:
 119 \:::Pro v¹echny hrany $(v,w)$ opakujeme:
 120 \::::Je-li $h(w) < h(v) + \ell(v,w)$:
 121 \:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
 122 \:::::$\<stav>(w)\leftarrow\<otevøen>$.
 123 \:Vrátíme výsledek $d(u,v)=h(v)$ pro v¹echna~$v$.
 124 \endalgo
 125
 126 Podobnì jako u~minimálních koster, i zde se jedná o~meta-algoritmus, proto¾e
 127 v~kroku~4 nespecifikuje, podle jakého pravidla se vrchol~$v$ vybírá. Pøesto
 128 ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu
 129 výbìru nezávisejí.
 130
 131 \>\s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak:
 132
 133 \numlist\nparen
 134 \:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu -- doká¾eme indukcí podle poètu krokù algoritmu.
 135 \:$h(v)$ dokonce odpovídá délce nìjaké cesty -- staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus.
 136 \:Algoritmus se v¾dy zastaví -- cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro
 137   ka¾dý~$v$, je koneènì mnoho.
 138 \:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$ --
 139   implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol,
 140   který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran.
 141 \:Po zastavení mají koneèné~$h(v)$ právì v¹echny uzavøené vrcholy.
 142 \:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$ -- kdyby to nebyla pravda,
 143   vyberme si ze~\uv{¹patných} vrcholù~$v$ takový, pro nìj¾ obsahuje nejkrat¹í cesta z~$u$ do~$v$
 144   nejmen¹í mo¾ný poèet hran. Vrchol~$v$ je zajisté rùzný od~$u$, tak¾e má na~této cestì nìjakého
 145   pøedchùdce~$w$. Pøitom~$w$ u¾ musí být ohodnocen správnì a relaxace, která mu toto ohodnocení
 146   nastavila, ho musela prohlásit za~otevøený. Jen¾e ka¾dý otevøený vrchol je pozdìji uzavøen,
 147   tak¾e~$w$ poté musel být je¹tì alespoò jednou relaxován, co¾ muselo sní¾it~$h(v)$ na správnou
 148   vzdálenost.
 149 \endlist
 150
 151 \>Meta-algoritmus tedy pro libovolnou implementaci kroku~4 spoèítá správné vzdálenosti.
 152 \qed
 153
 154 \>\s{Cvièení:}
 155 \itemize\ibull
 156 \:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9
 157   pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$u$. Doka¾te, ¾e pøedchùdci
 158   dosa¾itelných vrcholù budou tvoøit strom a ¾e tento strom bude stromem
 159   nejkrat¹ích cest z~vrcholu~$u$.
 160 \:Doka¾te, ¾e pro graf, v~nìm¾ je alespoò jeden záporný cyklus dosa¾itelný
 161   z~poèáteèního vrcholu, se algoritmus nezastaví a ohodnocení v¹ech vrcholù
 162   na cyklu postupnì klesnou libovolnì hluboko. Nedosa¾itelné záporné cykly
 163   chod algoritmu samozøejmì nijak neovlivní.
 164 \endlist
 165
 166 \h{Bellmanùv-Fordùv-Mooreùv algoritmus}
 167
 168 Bellman, Ford a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM),
 169 který lze v~øeèi na¹eho meta-algoritmu formulovat takto: Otevøené vrcholy
 170 udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané
 171 zaøazujeme na~konec. Co toto pravidlo zpùsobí?
 172
 173 \>\s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$.
 174
 175 \proof
 176 Bìh algoritmu rozdìlíme na~fáze. Nultá fáze sestává z~vlo¾ení vrcholu~$u$
 177 do~fronty. V~$(i+1)$-ní fázi relaxujeme ty vrcholy, které byly do~fronty
 178 ulo¾eny bìhem $i$-té fáze.
 179
 180 V¹imneme si, ¾e na~konci $i$-té fáze je ka¾dé ohodnocení $h(v)$ shora omezeno
 181 délkou nejkrat¹ího ze~sledù z~$u$ do~$v$, které mají nejvý¹e~$i$ hran. Fází je
 182 tedy nejvý¹e~$n$.
 183
 184 Relaxace ka¾dého vrcholu pøitom trvá lineárnì se stupnìm vrcholu, tak¾e celá
 185 fáze probìhne v~èase $\O(m)$.
 186 \qed
 187
 188 \>\s{Cvièení:}
 189 \itemize\ibull
 190 \:Uka¾te, ¾e asymptoticky stejné èasové slo¾itosti by dosáhl algoritmus,
 191   který by vrcholy oèísloval $v_1,\ldots,v_n$ a opakovanì by je v~tomto
 192   poøadí relaxoval tak dlouho, dokud by se ohodnocení mìnila.
 193 \:Jak algoritmus upravit, aby v~$i$-té fázi spoèítal minimální délky sledù
 194   o~právì~$i$ hranách?
 195 \:Jak lze algoritmus BFM vyu¾ít k~nalezení záporného cyklu?
 196 \endlist
 197
 198 \h{Dijkstrùv algoritmus}
 199
 200 Pokud jsou v¹echny délky hran nezáporné, mù¾eme pou¾ít efektivnìj¹í pravidlo
 201 pro výbìr vrcholu navr¾ené Dijkstrou. To øíká, ¾e v¾dy relaxujeme ten z~otevøených
 202 vrcholù, jeho¾ ohodnocení je nejmen¹í.
 203
 204 \>\s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající
 205 vzdálenosti od~$u$ a ka¾dý dosa¾itelný vrchol uzavøe právì jednou.
 206
 207 \proof
 208 Indukcí doká¾eme, ¾e v~ka¾dém okam¾iku mají v¹echny uzavøené vrcholy ohodnocení
 209 men¹í nebo rovné ohodnocením v¹ech otevøených vrcholù. Na~poèátku to jistì platí.
 210 Nech» nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevøenými. Bìhem jeho
 211 relaxace nemù¾eme ¾ádnou hodnotu sní¾it pod~$h(v)$, jeliko¾ v~grafu s~nezápornými
 212 hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevøených vrcholù
 213 tedy neklesne pod hodnotu tohoto novì uzavøeného. Hodnoty døíve uzavøených vrcholù
 214 se nemohou nijak zmìnit.
 215 \qed
 216
 217 Pøímoèará implementace Dijkstrova algoritmu by tedy poka¾dé v~èase $\O(n)$
 218 vybrala otevøený vrchol s~nejmen¹ím ohodnocením, v~èase $\O(n)$ ho relaxovala
 219 a toto by se opakovalo nejvý¹e $n$-krát. Algoritmus by tedy dobìhl v~èase $\O(n^2)$,
 220 co¾ je pro husté grafy zajisté optimální. Zkusíme tedy algoritmus zrychlit
 221 na~øídkých grafech.
 222
 223 V¹echny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, tak¾e úzkým hrdlem je
 224 vybírání minima. Pou¾ijeme tedy vhodnou datovou strukturu, v~ní¾ budeme udr¾ovat
 225 mno¾inu v¹ech otevøených vrcholù spolu s~jejich ohodnoceními. Od~datové struktury
 226 potøebujeme, aby umìla operace \<Insert> (vlo¾ení vrcholu), \<ExtractMin> (nalezení
 227 a smazání minima) a \<Decrease> (sní¾ení hodnoty vrcholu). První dvì operace pøitom
 228 voláme nejvý¹e $n$-krát a operaci \<Decrease> nejvý¹e $m$-krát. Celý algoritmus
 229 tedy dobìhne v~èase
 230 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
 231 kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou èasové slo¾itosti jednotlivých operací
 232 na~struktuøe o~nejvý¹e~$n$ prvcích (staèí amortizovanì).
 233
 234 \>Jaké mo¾nosti máme pro volbu struktury?
 235
 236 \itemize\ibull
 237 \:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
 238   celkem tedy $\O(n^2)$.
 239 \:{\I (binární) halda} -- v¹echny tøi operace umíme provést v~èase $\O(\log n)$, tak¾e celkem
 240   $\O(m\log n)$. To je pro husté grafy hor¹í, pro øídké lep¹í.
 241 \:{\I $k$-regulární halda} -- pokud haldu upravíme tak, ¾e ka¾dý vrchol bude mít a¾ $k$ synù,
 242   hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky smìrem nahoru,
 243   co¾ je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ov¹em \<ExtractMin> potøebuje
 244   zkoumat v¹echny syny ka¾dého nav¹tíveného prvku, tak¾e se zpomalí na $\O(k\log_k n)$.
 245
 246   Celková slo¾itost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba èleny se vyrovnají
 247   pro $k=m/n$, èím¾ získáme $\O(m\log_{m/n} n)$. Tento logaritmus je pøitom $\O(1)$,
 248   kdykoliv je $m\ge n^{1+\varepsilon}$ pro nìjaké~$\varepsilon>0$, tak¾e pro dostateènì
 249   husté grafy je algoritmus lineární.
 250
 251   (V¹imnìte si, ¾e pro $m\approx n^2$ algoritmus zvolí $k\approx n$, tak¾e halda degeneruje
 252   na jediné patro, tedy na pole, které se opravdu ukázalo jako optimální volba pro husté grafy.)
 253 \:{\I Fibonacciho halda} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má slo¾itost
 254   $\O(\log n)$ [v¹e amortizovanì]. Dijkstrùv algoritmus tedy dobìhne v~èase $\O(m + n\log n)$.
 255   To je lineární pro grafy s~hustotou $\Omega(\log n)$.
 256 \:{\I Datové struktury pro èísla omezeného rozsahu} -- prozkoumáme vzápìtí.
 257 \endlist
 258
 259 \>\s{Cvièení:}
 260
 261 \itemize\ibull
 262 \:Najdìte pøíklad nìjakého grafu se zápornými hranami (ale bez záporných cyklù),
 263   na~kterém Dijkstrùv algoritmus sel¾e.
 264 \:Rozmyslete si, ¾e pokud nevyu¾ijeme nìjaké speciální vlastnosti èísel (celoèíselnost,
 265   omezený rozsah), je mez $\O(m+n\log n)$ nejlep¹í mo¾ná, proto¾e Dijkstrovým algoritmem
 266   mù¾eme tøídit $n$-tici èísel.
 267 \:Jsou-li délky hran celoèíselné, mù¾eme se na Dijkstrùv algoritmus dívat i takto:
 268   Pøedstavme si, ¾e ka¾dou hranu nahradíme cestou tvoøenou hranami jednotkové délky
 269   a na vzniklý neohodnocený graf spustíme prohledávání do~¹íøky. To samozøejmì vydá
 270   správný výsledek, ale pomìrnì pomalu, proto¾e bude vìt¹inu èasu trávit posouváním
 271   vlny \uv{uvnitø} pùvodních hran. Mù¾eme si tedy pro ka¾dou pùvodní hranu naøídit
 272   \uv{budík}, který nám øekne, za~kolik posunutí vlny dospìjeme na~její konec.
 273   Doka¾te, ¾e tento algoritmus je ekvivalentní s~Dijkstrovým.
 274 \endlist
 275
 276 %\references
 277 \bye