13-dijkstra/13-dijkstra.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{13}{NejkratĹĄĂ cesty}{}
   4
   5 \def\ppsp{1-1}
   6 \def\sssp{1-$n$}
   7 \def\apsp{$n$-$n$}
   8 \def\astar{A\kern-0.15em *}
   9
  10 ProblĂŠm hledĂĄnĂ nejkratĹĄĂ cesty v~(obvykle ohodnocenĂŠm orientovanĂŠm) grafu
  11 provĂĄzĂ teorii grafovĂ˝ch algoritmĹŻ od~samĂ˝ch poÄ\8dĂĄtkĹŻ. ZĂĄkladnĂ algoritmy
  12 pro hledĂĄnĂ cest jsou nedĂlnou souÄ\8dĂĄstĂ zĂĄkladnĂch kursĹŻ programovĂĄnĂ
  13 a algoritmĹŻ, my se budeme vÄ\9bnovat zejmĂŠna rĹŻznĂ˝m jejich vylepĹĄenĂm.
  14
  15 UvaĹžujme tedy nÄ\9bjakĂ˝ orientovanĂ˝ graf, jehoĹž kaĹždĂĄ hrana~$e$ je opatĹ\99ena
  16 {\I dĂŠlkou} $\ell(e)\in{\bb R}$. MnoĹžinÄ\9b hran (tĹ\99eba sledu nebo cestÄ\9b)
  17 pak pĹ\99iĹ\99adĂme dĂŠlku rovnou souÄ\8dtu dĂŠlek jednotlivĂ˝ch hran.
  18
  19 Pro vrcholy $u,v$ definujeme jejich {\I vzdĂĄlenost} $d(u,v)$ jako nejmenĹĄĂ
  20 moĹžnou dĂŠlku cesty z~$u$ do~$v$ (jelikoĹž cest je v~grafu koneÄ\8dnÄ\9b mnoho,
  21 minimum vĹždy existuje). Pokud z~$u$ do~$v$ ĹžĂĄdnĂĄ cesta nevede, poloĹžĂme
  22 $d(u,v) := \infty$.
  23
  24 Obvykle se studujĂ nĂĄsledujĂcĂ tĹ\99i problĂŠmy:
  25
  26 \itemize\ibull
  27 \:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalĂŠzt nejkratĹĄĂ
  28   cestu z~danĂŠho vrcholu~$u$ do~danĂŠho vrcholu~$v$. (Pokud je nejkratĹĄĂch cest
  29   vĂce, tak libovolnou z~nich.)
  30 \:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro danĂ˝ vrchol~$u$ chceme
  31   nalĂŠzt nejkratĹĄĂ cesty do~vĹĄech ostatnĂch vrcholĹŻ.
  32 \:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajĂmajĂ nĂĄs nejkratĹĄĂ cesty
  33   mezi vĹĄemi dvojicemi vrcholĹŻ.
  34 \endlist
  35
  36 PĹ\99ekvapivÄ\9b, tak obecnÄ\9b, jak jsme si uvedenĂŠ problĂŠmy definovali, je neumĂme
  37 Ĺ\99eĹĄit v~polynomiĂĄlnĂm Ä\8dase: pro grafy, kterĂŠ mohou obsahovat hrany zĂĄpornĂ˝ch
  38 dĂŠlek bez jakĂ˝chkoliv omezenĂ, je totiĹž hledĂĄnĂ nejkratĹĄĂ cesty NP-tÄ\9bĹžkĂŠ
  39 (lze na~nÄ\9bj snadno pĹ\99evĂŠst existenci hamiltonovskĂŠ cesty). VĹĄechny znĂĄmĂŠ
  40 polynomiĂĄlnĂ algoritmy totiĹž mĂsto nejkratĹĄĂ cesty hledajĂ nejkratĹĄĂ sled
  41 -- nijak nekontrolujĂ, zda cesta neprojde jednĂm vrcholem vĂcekrĂĄt.
  42
  43 NaĹĄtÄ\9bstĂ pro nĂĄs je to v~grafech bez cyklĹŻ zĂĄpornĂŠ dĂŠlky totĂŠĹž: pokud se
  44 v~nalezenĂŠm sledu vyskytne cyklus, mĹŻĹžeme jej \uv{vystĹ\99ihnout} a tĂm zĂskat
  45 sled, kterĂ˝ nenĂ delĹĄĂ a~kterĂ˝ mĂĄ mĂŠnÄ\9b hran. KaĹždĂ˝ nejkratĹĄĂ sled tak
  46 mĹŻĹžeme upravit na~stejnÄ\9b dlouhou cestu.
  47 V~grafech bez zĂĄpornĂ˝ch cyklĹŻ je tedy jedno, zda hledĂĄme sled nebo cestu;
  48 naopak vyskytne-li se zĂĄpornĂ˝ cyklus dosaĹžitelnĂ˝ z~poÄ\8dĂĄteÄ\8dnĂho vrcholu,
  49 nejkratĹĄĂ sled ani neexistuje.
  50
  51 NavĂc se nĂĄm bude hodit, Ĺže kaĹždĂ˝ prefix nejkratĹĄĂ cesty je opÄ\9bt nejkratĹĄĂ
  52 cesta. JinĂ˝mi slovy pokud nÄ\9bkterĂĄ z~nejkratĹĄĂch cest z~$u$ do~$v$ vede
  53 pĹ\99es nÄ\9bjakĂ˝ vrchol~$w$, pak jejĂ Ä\8dĂĄst z~$u$ do~$w$ je jednou z~nejkratĹĄĂch
  54 cest z~$u$ do~$w$. (V~opaÄ\8dnĂŠm pĹ\99ĂpadÄ\9b bychom mohli Ăşsek $u\ldots w$ vymÄ\9bnit za~kratĹĄĂ.)
  55
  56 DĂky tĂŠto {\I prefixovĂŠ vlastnosti} mĹŻĹžeme pro kaĹždĂ˝ vrchol~$u$ sestrojit jeho {\I strom
  57 nejkratĹĄĂch cest}~${\cal T}(u)$. To je nÄ\9bjakĂ˝ podgraf grafu~$G$, kterĂ˝ mĂĄ tvar
  58 stromu zakoĹ\99enÄ\9bnĂŠho v~$u$ a orientovanĂŠho smÄ\9brem od~koĹ\99ene, a~platĂ pro nÄ\9bj, Ĺže
  59 pro kaĹždĂ˝ vrchol~$v$ je (jedinĂĄ) cesta z~$u$ do~$v$ v~tomto stromu jednou
  60 z~nejkratĹĄĂch cest z~$u$ do~$v$ v~pĹŻvodnĂm grafu.
  61
  62 \s{PozorovĂĄnĂ:} Strom nejkratĹĄĂch cest vĹždy existuje.
  63
  64 \proof
  65 NechĹĽ $u=v_1,\ldots,v_n$ jsou vĹĄechny vrcholy grafu~$G$. IndukcĂ budeme
  66 dokazovat, Ĺže pro kaĹždĂŠ~$i$ existuje strom~${\cal T}_i$, v~nÄ\9bmĹž se nachĂĄzejĂ nejkratĹĄĂ
  67 cesty z~vrcholu~$u$ do vrcholĹŻ $v_1,\ldots,v_i$. Pro $i=1$ staÄ\8dĂ uvĂĄĹžit
  68 strom obsahujĂcĂ jedinĂ˝ vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobĂme
  69 strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkratĹĄĂ cestu z~$u$ do~$v_i$
  70 a oznaÄ\8dĂme~$z$ poslednĂ vrchol na~tĂŠto cestÄ\9b, kterĂ˝ se jeĹĄtÄ\9b vyskytuje v~${\cal T}_{i-1}$.
  71 Ă\9asek nejkratĹĄĂ cesty od~$z$ do~$v_i$ pak pĹ\99idĂĄme do~${\cal T}_{i-1}$
  72 a dĂky prefixovĂŠ vlastnosti bude i cesta z~$u$ do~$v_i$ v~novĂŠm stromu
  73 nejkratĹĄĂ.
  74 \qed
  75
  76 ZbĂ˝vĂĄ se dohodnout, v~jakĂŠm tvaru majĂ naĹĄe algoritmy vydĂĄvat vĂ˝sledek.
  77 U~problĂŠmĹŻ typu \ppsp{} je nejjednoduĹĄĹĄĂ vypsat celou cestu, u~\sssp{} mĹŻĹžeme jako vĂ˝stup
  78 vydat strom nejkratĹĄĂch cest z~danĂŠho poÄ\8dĂĄtku (vĹĄimnÄ\9bte si, Ĺže staÄ\8dĂ
  79 uvĂŠst pĹ\99edchĹŻdce kaĹždĂŠho vrcholu), u~\apsp{} vydĂĄme strom nejkratĹĄĂch cest
  80 pro kaĹždĂ˝ ze~zdrojovĂ˝ch vrcholĹŻ.
  81
  82 Ä\8casto se ovĹĄem ukĂĄĹže, Ĺže podstatnĂĄ Ä\8dĂĄst problĂŠmu se skrĂ˝vĂĄ v~samotnĂŠm
  83 vĂ˝poÄ\8dtu vzdĂĄlenostĂ a sestrojenĂ pĹ\99edchĹŻdcĹŻ je triviĂĄlnĂm rozĹĄĂĹ\99enĂm algoritmu.
  84 Budeme tedy obvykle jen poÄ\8dĂtat vzdĂĄlenosti a samotnou rekonstrukci cest
  85 ponechĂĄme Ä\8dtenĂĄĹ\99i jako snadnĂŠ cviÄ\8denĂ.
  86
  87 \h{RelaxaÄ\8dnĂ algoritmus}
  88
  89 ZaÄ\8dnÄ\9bme problĂŠmem \sssp{} a oznaÄ\8dme~$u$ vĂ˝chozĂ vrchol. VÄ\9btĹĄina znĂĄmĂ˝ch
  90 algoritmĹŻ funguje tak, Ĺže pro kaĹždĂ˝ vrchol~$v$ udrĹžujĂ ohodnocenĂ $h(v)$,
  91 kterĂŠ v~kaĹždĂŠm okamĹžiku odpovĂdĂĄ dĂŠlce nÄ\9bjakĂŠho sledu z~$u$ do~$v$. PostupnÄ\9b
  92 toto ohodnocenĂ upravujĂ, aĹž se z~nÄ\9bj stane vzdĂĄlenost $d(u,v)$ a algoritmus
  93 se mĹŻĹže zastavit.
  94
  95 Vhodnou operacĂ pro vylepĹĄovĂĄnĂ ohodnocenĂ je takzvanĂĄ {\I relaxace.}
  96 Vybereme si nÄ\9bjakĂ˝ vrchol~$v$ a pro vĹĄechny jeho sousedy~$w$ spoÄ\8dĂtĂĄme
  97 $h(v) + \ell(v,w)$, tedy dĂŠlku sledu, kterĂ˝ vznikne rozĹĄĂĹ\99enĂm aktuĂĄlnĂho
  98 sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota menĹĄĂ neĹž~$h(w)$,
  99 tak jĂ $h(w)$ pĹ\99epĂĹĄeme.
 100
 101 Abychom zabrĂĄnili opakovanĂ˝m relaxacĂm tĂŠhoĹž vrcholu, kterĂŠ nic nezmÄ\9bnĂ,
 102 budeme rozliĹĄovat tĹ\99i stavy vrcholĹŻ: {\I nevidÄ\9bn} (jeĹĄtÄ\9b jsme ho nenavĹĄtĂvili),
 103 {\I otevĹ\99en} (zmÄ\9bnilo se ohodnocenĂ, Ä\8dasem chceme relaxovat) a {\I uzavĹ\99en}
 104 (uĹž jsme relaxovali a nenĂ potĹ\99eba znovu).
 105
 106 NĂĄĹĄ algoritmus bude fungovat nĂĄsledovnÄ\9b:
 107
 108 \algo
 109 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
 110 \:$\<stav>(*)\leftarrow\<nevidÄ\9bn>$, $\<stav>(u)\leftarrow\<otevĹ\99en>$.
 111 \:Dokud existujĂ otevĹ\99enĂŠ vrcholy, opakujeme:
 112 \::$v\leftarrow\hbox{libovolnĂ˝ otevĹ\99enĂ˝ vrchol}$.
 113 \::$\<stav>(v)\leftarrow\<uzavĹ\99en>$.
 114 \::Relaxujeme~$v$:
 115 \:::Pro vĹĄechny hrany $vw$ opakujeme:
 116 \::::Je-li $h(w) > h(v) + \ell(v,w)$:
 117 \:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
 118 \:::::$\<stav>(w)\leftarrow\<otevĹ\99en>$.
 119 \:VrĂĄtĂme vĂ˝sledek $d(u,v)=h(v)$ pro vĹĄechna~$v$.
 120 \endalgo
 121
 122 PodobnÄ\9b jako u~minimĂĄlnĂch koster, i zde se jednĂĄ o~meta-algoritmus, protoĹže
 123 v~kroku~4 nespecifikuje, kterĂ˝ z~otevĹ\99enĂ˝ch vrcholĹŻ vybĂrĂĄ. PĹ\99esto
 124 ale mĹŻĹžeme dokĂĄzat nÄ\9bkolik zajĂmavĂ˝ch tvrzenĂ, kterĂĄ na~konkrĂŠtnĂm zpĹŻsobu
 125 vĂ˝bÄ\9bru nezĂĄvisejĂ.
 126
 127 \s{VÄ\9bta:} SpustĂme-li meta-algoritmus na graf bez zĂĄpornĂ˝ch cyklĹŻ, pak:
 128
 129 \numlist\nparen
 130 \:OhodnocenĂ $h(v)$ vĹždy odpovĂdĂĄ dĂŠlce nÄ\9bjakĂŠho sledu z~$u$ do~$v$.
 131 \:$h(v)$ dokonce odpovĂdĂĄ dĂŠlce nÄ\9bjakĂŠ cesty z~$u$ do~$v$.
 132 \:Algoritmus se vĹždy zastavĂ.
 133 \:Po zastavenĂ jsou oznaÄ\8deny jako uzavĹ\99enĂŠ prĂĄvÄ\9b ty vrcholy, kterĂŠ jsou dosaĹžitelnĂŠ z~$u$.
 134 \:Po zastavenĂ majĂ koneÄ\8dnĂŠ~$h(v)$ prĂĄvÄ\9b vĹĄechny uzavĹ\99enĂŠ vrcholy.
 135 \:Pro kaĹždĂ˝ dosaĹžitelnĂ˝ vrchol je na~konci $h(v)$ rovno $d(u,v)$.
 136 \endlist
 137
 138 \proof
 139
 140 \numlist\nparen
 141 \:DokĂĄĹžeme indukcĂ podle poÄ\8dtu krokĹŻ algoritmu.
 142 \:StaÄ\8dĂ rozmyslet, v~jakĂŠ situaci by vytvoĹ\99enĂ˝ sled mohl obsahovat cyklus.
 143 \:Cest, a~tĂm pĂĄdem i moĹžnĂ˝ch hodnot~$h(v)$ pro kaĹždĂ˝~$v$, je koneÄ\8dnÄ\9b mnoho.
 144 \:Implikace $\Rightarrow$ je triviĂĄlnĂ, pro $\Leftarrow$ staÄ\8dĂ uvĂĄĹžit neuzavĹ\99enĂ˝ vrchol,
 145   kterĂ˝ je dosaĹžitelnĂ˝ z~$u$ cestou o~co nejmenĹĄĂm poÄ\8dtu hran.
 146 \:$h(v)$ nastavujeme na~koneÄ\8dnou hodnotu prĂĄvÄ\9b v~okamĹžicĂch, kdy se vrchol stĂĄvĂĄ otevĹ\99enĂ˝m.
 147   KaĹždĂ˝ otevĹ\99enĂ˝ vrchol je Ä\8dasem uzavĹ\99en.
 148 \:Kdyby tomu tak nebylo,
 149   vyberme si ze~\uv{ĹĄpatnĂ˝ch} vrcholĹŻ~$v$ takovĂ˝, pro nÄ\9bjĹž obsahuje nejkratĹĄĂ cesta z~$u$ do~$v$
 150   nejmenĹĄĂ moĹžnĂ˝ poÄ\8det hran. Vrchol~$v$ je zajistĂŠ rĹŻznĂ˝ od~$u$, takĹže mĂĄ na~tĂŠto cestÄ\9b nÄ\9bjakĂŠho
 151   pĹ\99edchĹŻdce~$w$. PĹ\99itom~$w$ uĹž musĂ bĂ˝t ohodnocen sprĂĄvnÄ\9b a relaxace, kterĂĄ mu toto ohodnocenĂ
 152   nastavila, ho musela prohlĂĄsit za~otevĹ\99enĂ˝. JenĹže kaĹždĂ˝ otevĹ\99enĂ˝ vrchol je pozdÄ\9bji uzavĹ\99en,
 153   takĹže~$w$ potĂŠ musel bĂ˝t jeĹĄtÄ\9b alespoĹ\88 jednou relaxovĂĄn, coĹž muselo snĂĹžit~$h(v)$ na sprĂĄvnou
 154   vzdĂĄlenost.
 155 \qeditem
 156 \endlist
 157
 158 \>DokĂĄzali jsme tedy, Ĺže meta-algoritmus pro libovolnou implementaci kroku~4
 159 spoÄ\8dĂtĂĄ sprĂĄvnĂŠ vzdĂĄlenosti.
 160
 161 \medskip
 162
 163 \s{CviÄ\8denĂ:}
 164 \itemize\ibull
 165 \:NechĹĽ do algoritmu doplnĂme udrĹžovĂĄnĂ pĹ\99edchĹŻdcĹŻ tak, Ĺže v~kroku~9
 166   pĹ\99enastavĂme pĹ\99edchĹŻdce vrcholu~$w$ na vrchol~$v$. DokaĹžte, Ĺže pĹ\99edchĹŻdci
 167   dosaĹžitelnĂ˝ch vrcholĹŻ budou tvoĹ\99it strom a Ĺže tento strom bude stromem
 168   nejkratĹĄĂch cest z~vrcholu~$u$.
 169 \:DokaĹžte, Ĺže pro graf, v~nÄ\9bmĹž je alespoĹ\88 jeden zĂĄpornĂ˝ cyklus dosaĹžitelnĂ˝
 170   z~poÄ\8dĂĄteÄ\8dnĂho vrcholu, se algoritmus nezastavĂ a ohodnocenĂ vĹĄech vrcholĹŻ
 171   na cyklu postupnÄ\9b klesnou libovolnÄ\9b hluboko. NedosaĹžitelnĂŠ zĂĄpornĂŠ cykly
 172   chod algoritmu samozĹ\99ejmÄ\9b nijak neovlivnĂ.
 173 \endlist
 174
 175 \h{BellmanĹŻv-FordĹŻv-MooreĹŻv algoritmus}
 176
 177 Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezĂĄvisle na sobÄ\9b algoritmus (Ĺ\99Ăkejme mu BFM),
 178 kterĂ˝ lze v~Ĺ\99eÄ\8di naĹĄeho meta-algoritmu formulovat takto: OtevĹ\99enĂŠ vrcholy
 179 udrĹžujeme ve~frontÄ\9b (vĹždy relaxujeme vrchol na poÄ\8dĂĄtku fronty, novÄ\9b otevĂranĂŠ
 180 zaĹ\99azujeme na~konec). Co toto pravidlo zpĹŻsobĂ?
 181
 182 \s{VÄ\9bta:} Ä\8casovĂĄ sloĹžitost algoritmu~BFM Ä\8dinĂ $\O(nm)$.
 183
 184 \proof
 185 BÄ\9bh algoritmu rozdÄ\9blĂme na~fĂĄze. NultĂĄ fĂĄze sestĂĄvĂĄ z~vloĹženĂ vrcholu~$u$
 186 do~fronty. V~$(i+1)$-nĂ fĂĄzi relaxujeme ty vrcholy, kterĂŠ byly do~fronty
 187 uloĹženy bÄ\9bhem $i$-tĂŠ fĂĄze.
 188
 189 JelikoĹž relaxace vrcholu trvĂĄ lineĂĄrnÄ\9b se stupnÄ\9bm vrcholu a kaĹždĂ˝ vrchol
 190 se danĂŠ fĂĄze ĂşÄ\8dastnĂ nejvĂ˝ĹĄe jednou, trvĂĄ jedna fĂĄze $\O(m)$. ZbĂ˝vĂĄ ukĂĄzat,
 191 Ĺže fĂĄzĂ provedeme nejvĂ˝ĹĄe~$n$.
 192
 193 IndukcĂ dokĂĄĹžeme, Ĺže na konci $i$-tĂŠ fĂĄze je kaĹždĂŠ ohodnocenĂ $h(v)$ shora omezeno
 194 dĂŠlkou nejkratĹĄĂho z~$uv$-sledĹŻ o~nejvĂ˝ĹĄe~$i$ hranĂĄch. Pro $i=0$ to triviĂĄlnÄ\9b
 195 platĂ. UvaĹžujme nynĂ vrchol~$v$ na konci $(i+1)$-nĂ fĂĄze a nÄ\9bjakĂ˝ nejkratĹĄĂ $uv$-sled~$P$
 196 o~$i+1$ hranĂĄch. OznaÄ\8dme $wv$ poslednĂ hranu tohoto sledu a $P'$ sled bez tĂŠto hrany,
 197 kterĂ˝ tedy mĂĄ dĂŠlku~$i$. Podle indukÄ\8dnĂho pĹ\99edpokladu je na konci $i$-tĂŠ fĂĄze
 198 $h(w)\le \ell(P')$. Tuto hodnotu zĂskalo $h(w)$ nejpozdÄ\9bji v~$i$-tĂŠ fĂĄzi, pĹ\99i tom jsme
 199 vrchol~$w$ otevĹ\99eli, takĹže jsme ho nejpozdÄ\9bji v~$(i+1)$-nĂ fĂĄzi zavĹ\99eli a relaxovali.
 200 Po tĂŠto relaxaci je ovĹĄem $h(v)\le h(w)+\ell(w,v)\le \ell(P') + \ell(w,v) = \ell(P)$.
 201 \qed
 202
 203 \s{CviÄ\8denĂ:}
 204 \itemize\ibull
 205 \:UkaĹžte, Ĺže asymptoticky stejnĂŠ Ä\8dasovĂŠ sloĹžitosti by dosĂĄhl algoritmus,
 206   kterĂ˝ by vrcholy oÄ\8dĂsloval $v_1,\ldots,v_n$ a opakovanÄ\9b by je v~tomto
 207   poĹ\99adĂ relaxoval tak dlouho, dokud by se ohodnocenĂ mÄ\9bnila.
 208 \:Jak algoritmus upravit, aby v~$i$-tĂŠ fĂĄzi spoÄ\8dĂtal minimĂĄlnĂ dĂŠlky sledĹŻ
 209   o~prĂĄvÄ\9b~$i$ hranĂĄch?
 210 \:Jak lze algoritmus BFM vyuĹžĂt k~nalezenĂ zĂĄpornĂŠho cyklu?
 211 \endlist
 212
 213 \h{DijkstrĹŻv algoritmus}
 214
 215 Pokud jsou vĹĄechny dĂŠlky hran nezĂĄpornĂŠ, mĹŻĹžeme pouĹžĂt efektivnÄ\9bjĹĄĂ pravidlo
 216 pro vĂ˝bÄ\9br vrcholu navrĹženĂŠ Dijkstrou \cite{dijkstra:mstandpath}. To Ĺ\99ĂkĂĄ, Ĺže vĹždy relaxujeme ten z~otevĹ\99enĂ˝ch
 217 vrcholĹŻ, jehoĹž ohodnocenĂ je nejmenĹĄĂ.
 218
 219 \s{VÄ\9bta:} DijkstrĹŻv algoritmus uzavĂrĂĄ vrcholy v~poĹ\99adĂ podle neklesajĂcĂ
 220 vzdĂĄlenosti od~$u$ a kaĹždĂ˝ dosaĹžitelnĂ˝ vrchol uzavĹ\99e prĂĄvÄ\9b jednou.
 221
 222 \proof
 223 IndukcĂ dokĂĄĹžeme, Ĺže v~kaĹždĂŠm okamĹžiku majĂ vĹĄechny uzavĹ\99enĂŠ vrcholy ohodnocenĂ
 224 menĹĄĂ nebo rovnĂŠ ohodnocenĂm vĹĄech otevĹ\99enĂ˝ch vrcholĹŻ. Na~poÄ\8dĂĄtku to jistÄ\9b platĂ.
 225 NechĹĽ nynĂ uzavĂrĂĄme vrchol~$v$ s~minimĂĄlnĂm $h(v)$ mezi otevĹ\99enĂ˝mi. BÄ\9bhem jeho
 226 relaxace nemĹŻĹžeme ĹžĂĄdnou hodnotu snĂĹžit pod~$h(v)$, jelikoĹž v~grafu s~nezĂĄpornĂ˝mi
 227 hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbĂ˝vajĂcĂch otevĹ\99enĂ˝ch vrcholĹŻ
 228 tedy neklesne pod hodnotu tohoto novÄ\9b uzavĹ\99enĂŠho. Hodnoty dĹ\99Ăve uzavĹ\99enĂ˝ch vrcholĹŻ
 229 se nemohou nijak zmÄ\9bnit.
 230 \qed
 231
 232 PĹ\99ĂmoÄ\8darĂĄ implementace Dijkstrova algoritmu by tedy pokaĹždĂŠ v~Ä\8dase $\O(n)$
 233 vybrala otevĹ\99enĂ˝ vrchol s~nejmenĹĄĂm ohodnocenĂm, v~Ä\8dase $\O(n)$ ho relaxovala
 234 a toto by se opakovalo nejvĂ˝ĹĄe $n$-krĂĄt. Algoritmus by tudĂĹž dobÄ\9bhl v~Ä\8dase $\O(n^2)$,
 235 coĹž je pro hustĂŠ grafy zajistĂŠ optimĂĄlnĂ. ZkusĂme nynĂ zrychlit vĂ˝poÄ\8det
 236 na~Ĺ\99ĂdkĂ˝ch grafech.
 237
 238 VĹĄechny relaxace trvajĂ dohromady $\O(\sum_v \deg(v)) = \O(m)$, takĹže ĂşzkĂ˝m hrdlem je
 239 vybĂrĂĄnĂ minima. PouĹžijeme pro nÄ\9bj vhodnou datovou strukturu, v~nĂĹž budeme udrĹžovat
 240 mnoĹžinu vĹĄech otevĹ\99enĂ˝ch vrcholĹŻ spolu s~jejich ohodnocenĂmi. Od~datovĂŠ struktury
 241 potĹ\99ebujeme, aby umÄ\9bla operace \<Insert> (vloĹženĂ vrcholu), \<ExtractMin> (nalezenĂ
 242 a smazĂĄnĂ minima) a \<Decrease> (snĂĹženĂ hodnoty vrcholu). PrvnĂ dvÄ\9b operace pĹ\99itom
 243 volĂĄme nejvĂ˝ĹĄe $n$-krĂĄt a operaci \<Decrease> nejvĂ˝ĹĄe $m$-krĂĄt. CelĂ˝ algoritmus
 244 tedy dobÄ\9bhne v~Ä\8dase
 245 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
 246 kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou Ä\8dasovĂŠ sloĹžitosti jednotlivĂ˝ch operacĂ
 247 na~struktuĹ\99e o~nejvĂ˝ĹĄe~$n$ prvcĂch (staÄ\8dĂ amortizovanÄ\9b).
 248
 249 \>JakĂŠ moĹžnosti mĂĄme pro volbu struktury?
 250
 251 \itemize\ibull
 252 \:{\I pole} -- \<Insert> a \<Decrease> stojĂ konstantu, \<ExtractMin> trvĂĄ $\O(n)$,
 253   celkem tedy $\O(n^2)$.
 254 \:{\I (binĂĄrnĂ) halda} -- vĹĄechny tĹ\99i operace umĂme provĂŠst v~Ä\8dase $\O(\log n)$, takĹže celkem
 255   $\O(m\log n)$. To je pro hustĂŠ grafy horĹĄĂ, pro Ĺ\99ĂdkĂŠ lepĹĄĂ.
 256 \:{\I $k$-regulĂĄrnĂ halda} -- pokud haldu upravĂme tak, Ĺže kaĹždĂ˝ prvek bude mĂt aĹž $k$ synĹŻ,
 257   hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublĂĄvajĂcĂ} prvky smÄ\9brem nahoru,
 258   coĹž je \<Insert> a \<Decrease>, se zrychlĂ na~$\O(\log_k n)$. OvĹĄem \<ExtractMin> potĹ\99ebuje
 259   zkoumat vĹĄechny syny kaĹždĂŠho navĹĄtĂvenĂŠho prvku, takĹže se zpomalĂ na $\O(k\log_k n)$.
 260
 261   CelkovĂĄ sloĹžitost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba Ä\8dleny se vyrovnajĂ
 262   pro $k=m/n$, Ä\8dĂmĹž zĂskĂĄme $\O(m\log_{m/n} n)$. Ä\8clen $\log_{m/n} n$ je pĹ\99itom $\O(1)$,
 263   kdykoliv je $m\ge n^{1+\varepsilon}$ pro nÄ\9bjakĂŠ~$\varepsilon>0$, takĹže pro dostateÄ\8dnÄ\9b
 264   hustĂŠ grafy jsme zĂskali lineĂĄrnĂ algoritmus.
 265
 266   (VĹĄimnÄ\9bte si, Ĺže pro $m\approx n^2$ algoritmus zvolĂ $k\approx n$, takĹže halda degeneruje
 267   na jedinĂŠ patro, tedy na pole, kterĂŠ se opravdu ukĂĄzalo bĂ˝t optimĂĄlnĂ volbou pro hustĂŠ grafy.)
 268 \:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojĂ $\O(1)$, \<ExtractMin> mĂĄ sloĹžitost
 269   $\O(\log n)$ [vĹĄe amortizovanÄ\9b]. DijkstrĹŻv algoritmus proto dobÄ\9bhne v~Ä\8dase $\O(m + n\log n)$.
 270   To je lineĂĄrnĂ pro grafy s~hustotou $\Omega(\log n)$. TĂŠĹže sloĹžitosti operacĂ dosahujĂ
 271   i jinĂŠ, mĂŠnÄ\9b znĂĄmĂŠ haldy \cite{haeupler:rankph,elmasry:violheap}, kterĂŠ mohou bĂ˝t v~praxi
 272   vĂ˝raznÄ\9b rychlejĹĄĂ.
 273 \:{\I MonotĂłnnĂ haldy} -- mĹŻĹžeme pouĹžĂt nÄ\9bjakou jinou haldu, kterĂĄ vyuĹžĂvĂĄ toho,
 274   Ĺže posloupnost odebĂranĂ˝ch prvkĹŻ je neklesajĂcĂ. Pro celĂĄ Ä\8dĂsla na~\hbox{RAMu} to mĹŻĹže
 275   bĂ˝t napĹ\99Ăklad Thorupova halda \cite{thorup:queue} se sloĹžitostĂ $\O(\log\log n)$ u~operace \<ExtractMin>
 276   a $\O(1)$ u~ostatnĂch operacĂ. Dijkstra tedy bÄ\9bĹžĂ v~$\O(m + n\log\log n)$.
 277 \:{\I DatovĂŠ struktury pro omezenĂŠ universum} -- prozkoumĂĄme vzĂĄpÄ\9btĂ.
 278 \endlist
 279
 280 \s{CviÄ\8denĂ:}
 281
 282 \itemize\ibull
 283 \:NajdÄ\9bte pĹ\99Ăklad grafu se zĂĄpornĂ˝mi hranami (ale bez zĂĄpornĂ˝ch cyklĹŻ),
 284   na~kterĂŠm DijkstrĹŻv algoritmus selĹže.
 285 \:Rozmyslete si, Ĺže pokud nevyuĹžijeme nÄ\9bjakĂŠ speciĂĄlnĂ vlastnosti Ä\8dĂsel (celoÄ\8dĂselnost,
 286   omezenĂ˝ rozsah), je mez $\O(m+n\log n)$ nejlepĹĄĂ moĹžnĂĄ, protoĹže DijkstrovĂ˝m algoritmem
 287   mĹŻĹžeme tĹ\99Ădit $n$-tici Ä\8dĂsel. Thorup dokonce dokĂĄzal \cite{thorup:equiv}, Ĺže z~kaĹždĂŠho tĹ\99ĂdĂcĂho algoritmu
 288   se sloĹžitostĂ $\O(nT(n))$ mĹŻĹžeme odvodit haldu se sloĹžitostĂ mazĂĄnĂ $\O(T(n))$.
 289 \:Jsou-li dĂŠlky hran celoÄ\8dĂselnĂŠ, mĹŻĹžeme se na DijkstrĹŻv algoritmus dĂvat i takto:
 290   PĹ\99edstavme si, Ĺže kaĹždou hranu nahradĂme cestou tvoĹ\99enou pĹ\99ĂsluĹĄnĂ˝m poÄ\8dtem hran jednotkovĂŠ dĂŠlky
 291   a na vzniklĂ˝ neohodnocenĂ˝ graf spustĂme prohledĂĄvĂĄnĂ do~ĹĄĂĹ\99ky. To samozĹ\99ejmÄ\9b vydĂĄ
 292   sprĂĄvnĂ˝ vĂ˝sledek, ale pomÄ\9brnÄ\9b pomalu, protoĹže bude vÄ\9btĹĄinu Ä\8dasu trĂĄvit posouvĂĄnĂm
 293   vlny \uv{uvnitĹ\99} pĹŻvodnĂch hran. MĹŻĹžeme si tedy pro kaĹždou pĹŻvodnĂ hranu naĹ\99Ădit
 294   \uv{budĂk}, kterĂ˝ nĂĄm Ĺ\99ekne, za~kolik posunutĂ vlny dospÄ\9bjeme na~jejĂ konec.
 295   DokaĹžte, Ĺže tento algoritmus je ekvivalentnĂ s~DijkstrovĂ˝m.
 296 \endlist
 297
 298 \h{CeloÄ\8dĂselnĂŠ dĂŠlky}
 299
 300 UvaĹžujme nynĂ grafy, v~nichĹž jsou vĹĄechny dĂŠlky hran nezĂĄpornĂĄ celĂĄ Ä\8dĂsla omezenĂĄ
 301 nÄ\9bjakou konstantou~$L$. VĹĄechny vzdĂĄlenosti jsou tedy omezeny Ä\8dĂslem~$nL$, takĹže
 302 nĂĄm staÄ\8dĂ datovĂĄ struktura schopnĂĄ uchovĂĄvat takto omezenĂĄ celĂĄ Ä\8dĂsla.
 303
 304 PouĹžijeme jednoduchou pĹ\99ihrĂĄdkovou strukturu: pole indexovanĂŠ hodnotami od~0 do~$nL$,
 305 jeho $i$-tĂ˝ prvek bude obsahovat seznam vrcholĹŻ, jejichĹž ohodnocenĂ je rovno~$i$.
 306 Operace \<Insert> a \<Decrease> zvlĂĄdneme v~konstantnĂm Ä\8dase, budeme-li si u~kaĹždĂŠho
 307 prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potĹ\99ebuje najĂt prvnĂ
 308 neprĂĄzdnou pĹ\99ihrĂĄdku, ale jelikoĹž vĂme, Ĺže posloupnost odebĂranĂ˝ch minim je monotĂłnnĂ,
 309 staÄ\8dĂ hledat od mĂsta, kde se hledĂĄnĂ zastavilo minule. VĹĄechna hledĂĄnĂ pĹ\99ihrĂĄdek
 310 tedy zaberou dohromady $\O(nL)$ a celĂ˝ DijkstrĹŻv algoritmus bude trvat $\O(nL + m)$.
 311
 312 ProstorovĂĄ sloĹžitost $\O(nL+m)$ je nevalnĂĄ, ale mĹŻĹžeme ji jednoduchĂ˝m trikem
 313 snĂĹžit: VĹĄimneme si, Ĺže vĹĄechna koneÄ\8dnĂĄ ohodnocenĂ vrcholĹŻ nemohou bĂ˝t vÄ\9btĹĄĂ
 314 neĹž aktuĂĄlnĂ minimum zvÄ\9btĹĄenĂŠ o~$L$. JinĂ˝mi slovy vĹĄechny neprĂĄzdnĂŠ pĹ\99ihrĂĄdky
 315 se nachĂĄzejĂ v~Ăşseku pole dlouhĂŠm~$L+1$, takĹže staÄ\8dĂ indexovat modulo~$L+1$.
 316 Pouze si musĂme dĂĄvat pozor, abychom sprĂĄvnÄ\9b poznali, kdy se struktura
 317 vyprĂĄzdnila, coĹž zjistĂme napĹ\99Ăklad pomocĂ poÄ\8dĂtadla otevĹ\99enĂ˝ch vrcholĹŻ. Ä\8cas si
 318 asymptoticky nezhorĹĄĂme, prostor klesne na~$\O(L+m)$.
 319
 320 PodobnĂ˝ trik mĹŻĹžeme pouĹžĂt i pro libovolnou jinou datovou strukturu: rozsah Ä\8dĂsel
 321 rozdÄ\9blĂme na~\uv{okna} velikosti~$L$ (v~$i$-tĂŠm oknÄ\9b jsou Ä\8dĂsla $iL,iL+1,\ldots,(i+1)L-1$).
 322 V~libovolnĂŠ chvĂli mohou tedy bĂ˝t neprĂĄzdnĂĄ nejvĂ˝ĹĄe dvÄ\9b okna. StaÄ\8dĂ nĂĄm proto
 323 poĹ\99Ădit si dvÄ\9b struktury pro uklĂĄdĂĄnĂ Ä\8dĂsel v~rozsahu $0,\ldots,L-1$ -- jedna
 324 z~nich bude reprezentovat aktuĂĄlnĂ okno (to, v~nÄ\9bmĹž leĹželo minulĂŠ minimum),
 325 druhĂĄ okno bezprostĹ\99ednÄ\9b nĂĄsledujĂcĂ. Minimum maĹžeme z~prvnĂ struktury; pokud
 326 uĹž je prĂĄzdnĂĄ, obÄ\9b struktury prohodĂme. Operace \<Insert> podle hodnoty urÄ\8dĂ,
 327 do~kterĂŠ struktury se mĂĄ vklĂĄdat. S~operacĂ \<Decrease> je to sloĹžitÄ\9bjĹĄĂ --
 328 hodnota z~vyĹĄĹĄĂ struktury mĹŻĹže pĹ\99eskoÄ\8dit do tĂŠ niĹžĹĄĂ, ale v~takovĂŠm pĹ\99ĂpadÄ\9b
 329 ji ve~vyĹĄĹĄĂ struktuĹ\99e vymaĹžeme (to je \<Decrease> na $-\infty$ nĂĄsledovanĂ˝
 330 \<ExtractMin>em) a do~tĂŠ niĹžĹĄĂ vloĹžĂme. To se kaĹždĂŠmu prvku mĹŻĹže pĹ\99ihodit nejvĂ˝ĹĄe
 331 jednou, takĹže stĂĄle platĂ, Ĺže se kaĹždĂ˝ prvek ĂşÄ\8dastnĂ $\O(1)$ vloĹženĂ a $\O(1)$
 332 extrakcĂ minima.
 333
 334 UkĂĄzali jsme tedy, Ĺže pro naĹĄe potĹ\99eby postaÄ\8duje struktura schopnĂĄ uchovĂĄvĂĄnĂ
 335 Ä\8dĂsel menĹĄĂch nebo rovnĂ˝ch~$L$.
 336
 337 NabĂzĂ se pouĹžĂt van Emde-BoasĹŻv strom z~kapitoly o~vĂ˝poÄ\8detnĂch modelech.
 338 Ten dosahuje sloĹžitosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
 339 operaci \<Decrease> musĂme pĹ\99eklĂĄdat na \<Delete> a \<Insert>. CelkovĂĄ
 340 sloĹžitost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, pĹ\99iÄ\8demĹž Ä\8das~$L$
 341 spotĹ\99ebujeme na inicializaci struktury (tĂŠ se lze za jistĂ˝ch podmĂnek vyhnout,
 342 viz zmĂnÄ\9bnĂĄ kapitola).
 343
 344 VraĹĽme se ale jeĹĄtÄ\9b k~vyuĹžitĂ pĹ\99ihrĂĄdek\dots
 345
 346 \h{VĂceĂşrovĹ\88ovĂŠ pĹ\99ihrĂĄdky}
 347
 348 PodobnÄ\9b jako u~tĹ\99ĂdÄ\9bnĂ Ä\8dĂsel, i~zde se vyplĂĄcĂ stavÄ\9bt pĹ\99ihrĂĄdkovĂŠ struktury
 349 vĂceĂşrovĹ\88ovÄ\9b (pĹŻvodnÄ\9b popsĂĄno Goldbergem a Silversteinem \cite{goldberg:mlb}).
 350 JednotlivĂŠ hodnoty budeme zapisovat v~soustavÄ\9b o~zĂĄkladu~$B$,
 351 kterĂ˝ zvolĂme jako nÄ\9bjakou mocninu dvojky, abychom mohli s~Ä\8dĂslicemi tohoto
 352 zĂĄpisu snadno zachĂĄzet pomocĂ bitovĂ˝ch operacĂ. KaĹždĂŠ Ä\8dĂslo tedy zabere nejvĂ˝ĹĄe
 353 $d=1+\lfloor\log_B L\rfloor$ Ä\8dĂslic; pokud bude kratĹĄĂ, doplnĂme ho zleva nulami.
 354
 355 NejvyĹĄĹĄĂ patro struktury bude tvoĹ\99eno polem $B$~pĹ\99ihrĂĄdek, v~$i$-tĂŠ z~nich
 356 budou uloĹžena ta Ä\8dĂsla, jejichĹž Ä\8dĂslice nejvyĹĄĹĄĂho Ĺ\99ĂĄdu je rovna~$i$. Za~{\I aktivnĂ}
 357 prohlĂĄsĂme tu pĹ\99ihrĂĄdku, kterĂĄ obsahuje aktuĂĄlnĂ minimum. PĹ\99ihrĂĄdky s~menĹĄĂmi
 358 indexy jsou prĂĄzdnĂŠ a zĹŻstanou takovĂŠ aĹž do~konce vĂ˝poÄ\8dtu, protoĹže halda
 359 je monotĂłnnĂ. Pokud v~pĹ\99ihrĂĄdce obsahujĂcĂ minimum bude vĂce prvkĹŻ, budeme
 360 ji rozklĂĄdat podle druhĂŠho nejvyĹĄĹĄĂho Ĺ\99ĂĄdu na dalĹĄĂch~$B$ pĹ\99ihrĂĄdek atd.
 361 Celkem tak vznikne aĹž~$d$ ĂşrovnĂ.
 362
 363 \>Struktura bude obsahovat nĂĄsledujĂcĂ data:
 364
 365 \itemize\ibull
 366 \:Parametry $L$, $B$ a~$d$.
 367 \:Pole ĂşrovnĂ (nejvyĹĄĹĄĂ mĂĄ Ä\8dĂslo~$d-1$, nejniĹžĹĄĂ~0), kaĹždĂĄ ĂşroveĹ\88 je buÄ\8fto prĂĄzdnĂĄ
 368   (a pak jsou prĂĄzdnĂŠ i~vĹĄechny niĹžĹĄĂ), nebo obsahuje pole~$U_i$ o~$B$ pĹ\99ihrĂĄdkĂĄch
 369   a v~kaĹždĂŠ z~nich seznam prvkĹŻ. Pole ĂşrovnĂ pouĹžĂvĂĄme jako zĂĄsobnĂk, udrĹžujeme
 370   si Ä\8dĂslo nejniĹžĹĄĂ neprĂĄzdnĂŠ ĂşrovnÄ\9b.
 371 \:Hodnotu~$\mu$ pĹ\99edchozĂho odebranĂŠho minima.
 372 \endlist
 373
 374 Operace \<Insert> vloĹžĂ hodnotu do~nejhlubĹĄĂ moĹžnĂŠ pĹ\99ihrĂĄdky. PodĂvĂĄ se tedy
 375 na~nejvyĹĄĹĄĂ ĂşroveĹ\88: pokud hodnota patĹ\99Ă do pĹ\99ihrĂĄdky, kterĂĄ nenĂ aktivnĂ, vloĹžĂ
 376 ji pĹ\99Ămo. Jinak pĹ\99ejde o~ĂşroveĹ\88 nĂĹže a zopakuje stejnĂ˝ postup. To vĹĄe lze provĂŠst
 377 v~konstantnĂm Ä\8dase: staÄ\8dĂ se podĂvat, jakĂ˝ je nejvyĹĄĹĄĂ jedniÄ\8dkovĂ˝ bit ve~{\sc xor}u
 378 novĂŠ hodnoty s~Ä\8dĂslem~$\mu$ (opÄ\9bt viz kapitola o~vĂ˝poÄ\8detnĂch modelech), a tĂm zjistit
 379 Ä\8dĂslo ĂşrovnÄ\9b, kam hodnota patĹ\99Ă.
 380
 381 Pokud chceme provĂŠst \<Decrease>, odstranĂme hodnotu z~pĹ\99ihrĂĄdky, ve~kterĂŠ se
 382 prĂĄvÄ\9b nachĂĄzĂ (polohu si mĹŻĹžeme u~kaĹždĂŠ hodnoty pamatovat zvlĂĄĹĄĹĽ), a znovu ji
 383 vloĹžĂme.
 384
 385 VÄ\9btĹĄinu prĂĄce samozĹ\99ejmÄ\9b pĹ\99enechĂĄme funkci \<ExtractMin>. Ta zaÄ\8dne prohledĂĄvat
 386 nejniĹžĹĄĂ obsazenou ĂşroveĹ\88 od~aktivnĂ pĹ\99ihrĂĄdky dĂĄl (to, kterĂĄ pĹ\99ihrĂĄdka je na
 387 kterĂŠ Ăşrovni aktivnĂ, poznĂĄme z~Ä\8dĂslic hodnoty~$\mu$). Pokud pĹ\99ihrĂĄdky na~tĂŠto
 388 Ăşrovni dojdou, prĂĄzdnou ĂşroveĹ\88 zruĹĄĂme a pokraÄ\8dujeme o~patro vĂ˝ĹĄe.
 389
 390 Jakmile najdeme neprĂĄzdnou pĹ\99ihrĂĄdku, nalezneme v~nĂ minimum a to se stane novĂ˝m~$\mu$.
 391 Pokud v~pĹ\99ihrĂĄdce nebyly ĹžĂĄdnĂŠ dalĹĄĂ prvky, skonÄ\8dĂme. V~opaÄ\8dnĂŠm pĹ\99ĂpadÄ\9b zbĂ˝vajĂcĂ
 392 prvky rozprostĹ\99eme do~pĹ\99ihrĂĄdek na~bezprostĹ\99ednÄ\9b niĹžĹĄĂ Ăşrovni, kterou tĂm zaloĹžĂme.
 393
 394 Ä\8cas strĂĄvenĂ˝ hledĂĄnĂm minima mĹŻĹžeme rozdÄ\9blit na~nÄ\9bkolik Ä\8dĂĄstĂ:
 395
 396 \itemize\ibull
 397 \:$\O(B)$ na inicializaci novĂŠ ĂşrovnÄ\9b -- to naĂşÄ\8dtujeme prvku, kterĂ˝ jsme
 398   prĂĄvÄ\9b mazali;
 399 \:hledĂĄnĂ neprĂĄzdnĂ˝ch pĹ\99ihrĂĄdek -- prozkoumĂĄnĂ kaĹždĂŠ prĂĄzdnĂŠ pĹ\99ihrĂĄdky
 400   naĂşÄ\8dtujeme jejĂmu vytvoĹ\99enĂ, coĹž se rozpustĂ v~$\O(B)$ na inicializaci
 401   ĂşrovnÄ\9b;
 402 \:zruĹĄenĂ ĂşrovnÄ\9b -- opÄ\9bt naĂşÄ\8dtujeme jejĂmu vzniku;
 403 \:rozhazovĂĄnĂ prvkĹŻ do pĹ\99ihrĂĄdek -- jelikoĹž prvky v~hierarchii pĹ\99ihrĂĄdek
 404   putujĂ bÄ\9bhem operacĂ pouze doleva a dolĹŻ (jejich hodnoty se nikdy nezvÄ\9btĹĄujĂ),
 405   klesne kaĹždĂ˝ prvek nejvĂ˝ĹĄe~$d$-krĂĄt, takĹže staÄ\8dĂ, kdyĹž na vĹĄechna rozhazovĂĄnĂ
 406   pĹ\99ispÄ\9bje Ä\8dasem $\O(d)$.
 407 \endlist
 408
 409 \>StaÄ\8dĂ tedy, aby kaĹždĂ˝ prvek pĹ\99i \<Insert>u zaplatil Ä\8das $\O(B+d)$ a jak \<Decrease>,
 410 tak \<ExtractMin> budou mĂt konstantnĂ amortizovanou sloĹžitost. DijkstrĹŻv
 411 algoritmus pak pobÄ\9bĹžĂ v~$\O(m + n(B+d))$.
 412
 413 ZbĂ˝vĂĄ nastavit parametry tak, abychom minimalizovali vĂ˝raz $B+d = B + \log L/\log B$.
 414 VhodnĂĄ volba je $B=\log L/\log\log L$. PĹ\99i nĂ platĂ
 415 $$
 416 {\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
 417 = {\log L\over \log\log L - \log\log\log L} = \Theta(B).
 418 $$
 419 Tehdy Dijkstra vydĂĄ vĂ˝sledek v~Ä\8dase $\O(m + n\cdot{\log L\over\log\log L})$.
 420
 421 \h{HOT Queue -- kombinace pĹ\99ihrĂĄdek s~haldou}
 422
 423 Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si vĹĄimli, Ĺže ve~vĂceĂşrovĹ\88ovĂ˝ch pĹ\99ihrĂĄdkovĂ˝ch strukturĂĄch
 424 platĂme pĹ\99ĂliĹĄ mnoho za~ĂşrovnÄ\9b, ve~kterĂ˝ch se za~dobu jejich existence objevĂ jen malĂŠ
 425 mnoĹžstvĂ prvkĹŻ. Navrhli tedy uklĂĄdat prvky z~\uv{malĂ˝ch} ĂşrovnĂ do~spoleÄ\8dnĂŠ haldy.
 426 VĂ˝slednĂŠ struktuĹ\99e se Ĺ\99ĂkĂĄ HOT (Heap-on-Top) Queue. My si pĹ\99edvedeme jejĂ upravenou
 427 variantu (v~tĂŠ pĹŻvodnĂ se skrĂ˝vĂĄ nÄ\9bkolik chyb).
 428
 429 PoĹ\99ĂdĂme si haldu, Ĺ\99eknÄ\9bme Fibonacciho, a~navĂc ke~kaĹždĂŠ Ăşrovni poÄ\8dĂtadlo udĂĄvajĂcĂ,
 430 kolik prvkĹŻ z~tĂŠto ĂşrovnÄ\9b jsme uloĹžili do~haldy. Dokud toto poÄ\8dĂtadlo nepĹ\99eroste nÄ\9bjakĂ˝
 431 parametr~$H$, pĹ\99ihrĂĄdky nebudeme zaklĂĄdat a prvky poputujĂ do~haldy. Ä\8cas $\O(B)$ na
 432 zaloĹženĂ ĂşrovnÄ\9b a jejĂ prochĂĄzenĂ proto mĹŻĹžeme rozpoÄ\8dĂtat mezi~$H$ prvkĹŻ, kterĂŠ se musely
 433 na~danĂŠ Ăşrovni objevit, neĹž byla rozpĹ\99ihrĂĄdkovĂĄna. (PovĹĄimnÄ\9bte si, Ĺže poÄ\8dĂtadlo nikdy
 434 nesniĹžujeme, pouze ho vynulujeme, kdyĹž je ĂşroveĹ\88 zruĹĄena. Proto vĹŻbec nemusĂ odpovĂdat
 435 skuteÄ\8dnĂŠmu poÄ\8dtu prvkĹŻ z~pĹ\99ĂsluĹĄnĂŠ ĂşrovnÄ\9b, kterĂŠ jsou prĂĄvÄ\9b uloĹženy v~haldÄ\9b. To ovĹĄem
 436 vĹŻbec nevadĂ -- poÄ\8dĂtadlo pouze hlĂdĂĄ, aby se ĂşroveĹ\88 nevytvoĹ\99ila pĹ\99ĂliĹĄ brzy, tedy abychom
 437 mÄ\9bli dost prvkĹŻ k~rozĂşÄ\8dtovĂĄnĂ Ä\8dasu.)
 438
 439 PromÄ\9bnnou~$\mu$ nechĂĄme ukazovat na~mĂsto, kde jsme se pĹ\99i hledĂĄnĂ minima v~pĹ\99ihrĂĄdkĂĄch
 440 zastavili. SouÄ\8dasnĂŠ globĂĄlnĂ minimum struktury mĹŻĹže bĂ˝t niĹžĹĄĂ, nachĂĄzĂ-li se minimum
 441 zrovna v~haldÄ\9b. StĂĄle je vĹĄak zaruÄ\8deno, Ĺže pĹ\99ed~$\mu$ se nenachĂĄzĂ ĹžĂĄdnĂĄ
 442 neprĂĄzdnĂĄ pĹ\99ihrĂĄdka.
 443
 444 Operace budou fungovat takto:
 445
 446 \>\<Insert>:
 447 \algo
 448 \:SpoÄ\8dĂtĂĄme, do~kterĂŠ ĂşrovnÄ\9b~$i$ mĂĄ prvek padnout (bitovĂ˝mi operacemi).
 449 \:Pokud je poÄ\8dĂtadlo tĂŠto ĂşrovnÄ\9b menĹĄĂ neĹž~$H$, zvĂ˝ĹĄĂme ho, vloĹžĂme prvek do~haldy a skoÄ\8dĂme.
 450 \:Nebyly-li jeĹĄtÄ\9b pro tuto ĂşroveĹ\88 zaloĹženy pĹ\99ihrĂĄdky, vyrobĂme prĂĄzdnĂŠ.
 451 \:VloĹžĂme prvek do~pĹ\99ĂsluĹĄnĂŠ pĹ\99ihrĂĄdky.
 452 \endalgo
 453
 454 \>\<Decrease>:
 455 \algo
 456 \:Pokud se prvek nachĂĄzĂ v~haldÄ\9b (to si u~kaĹždĂŠho prvku pamatujeme), provedeme
 457   \<Decrease> v~haldÄ\9b a skonÄ\8dĂme.
 458 \:SmaĹžeme prvek z~jeho pĹ\99ihrĂĄdky a provedeme \<Insert> s~novou hodnotou.
 459 \endalgo
 460
 461 \>\<ExtractMin>:
 462 \algo
 463 \:Dokud je~$\mu$ menĹĄĂ neĹž aktuĂĄlnĂ minimum haldy, opakujeme:
 464 \::Najdeme pĹ\99ihrĂĄdku odpovĂdajĂcĂ hodnotÄ\9b~$\mu$.
 465 \::Je-li tato pĹ\99ihrĂĄdka prĂĄzdnĂĄ, pĹ\99ejdeme na~dalĹĄĂ (upravĂme~$\mu$). Jsme-li na konci ĂşrovnÄ\9b,
 466    zruĹĄĂme ji, vynulujeme jejĂ poÄ\8dĂtadlo a pokraÄ\8dujeme o~ĂşroveĹ\88 vĂ˝ĹĄ.
 467 \::NenĂ-li prĂĄzdnĂĄ, rozprostĹ\99eme ji o~ĂşroveĹ\88 nĂĹž (stejnĂ˝m zpĹŻsobem jako pĹ\99i \<Insert>u,
 468    takĹže prvnĂch~$H$ prvkĹŻ vloĹžĂme do~haldy).
 469 \:SmaĹžeme minimum z~haldy a vrĂĄtĂme ho jako vĂ˝sledek.
 470 \endalgo
 471
 472 \>PustĂme se do~analĂ˝zy sloĹžitosti. Jako parametry si zvolĂme poÄ\8det hladin~$d$ (takĹže
 473 poÄ\8det pĹ\99ihrĂĄdek~$B$ na jednĂŠ Ăşrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
 474
 475 Nejprve si vĹĄimneme, Ĺže neĹž poÄ\8dĂtadlo nÄ\9bjakĂŠ ĂşrovnÄ\9b vynulujeme, jsou bezpeÄ\8dnÄ\9b
 476 z~haldy pryÄ\8d vĹĄechny prvky patĹ\99ĂcĂ do~tĂŠto ĂşrovnÄ\9b. Celkem se tedy v~haldÄ\9b
 477 vyskytuje nejvĂ˝ĹĄe $\O(dH)$ prvkĹŻ. \<ExtractMin> v~haldÄ\9b proto trvĂĄ $\O(\log(dH))$,
 478 ostatnĂ haldovĂŠ operace $\O(1)$.
 479
 480 NynĂ rozĂşÄ\8dtujeme Ä\8das operacĂ mezi jednotlivĂŠ prvky (opÄ\9bt si vĹĄe pĹ\99edplatĂme
 481 v~\<Insert>u a ostatnĂ operace pobÄ\9bĹžĂ v~amortizovanÄ\9b konstantnĂm Ä\8dase):
 482
 483 \itemize\ibull
 484 \:KaĹždĂ˝ prvek mĹŻĹže bĂ˝t nejvĂ˝ĹĄe jednou za~dobu svĂŠho Ĺživota vloĹžen do~haldy
 485   a nejvĂ˝ĹĄe jednou z~nĂ vyjmut. Na~obojĂ dohromady pĹ\99ispÄ\9bje $\O(\log dH)$.
 486 \:Prvek se ĂşÄ\8dastnĂ nejvĂ˝ĹĄe~$d$ pĹ\99ehozenĂ do~niĹžĹĄĂ ĂşrovnÄ\9b. Pokud byl pĹ\99ihozen
 487   do~haldy, uĹž tam setrvĂĄ, jinak pokaĹždĂŠ zaplatĂ $\O(1)$ za~zaĹ\99azenĂ do~pĹ\99ihrĂĄdky,
 488   celkem tedy $\O(d)$ na prvek.
 489 \:VytvoĹ\99enĂ, projitĂ a smazĂĄnĂ pĹ\99ihrĂĄdek na~jednĂŠ Ăşrovni nastane aĹž tehdy, co bylo
 490   $H$~prvkĹŻ patĹ\99ĂcĂch do~tĂŠto ĂşrovnÄ\9b vloĹženo do~haldy. StaÄ\8dĂ tedy, aby kaĹždĂ˝
 491   prvek pĹ\99ispÄ\9bl Ä\8dasem $\O(B/H) = \O(L^{1/d}/H)$.
 492 \endlist
 493
 494 \>KaĹždĂ˝ prvek tedy platĂ $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
 495 PojÄ\8fme najĂt nastavenĂ parametrĹŻ, kterĂŠ tento vĂ˝raz minimalizuje.
 496 Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
 497 CelĂ˝ vĂ˝raz tĂm zjednoduĹĄĂme na $\O(d + \log\,(L^{1/d}/d))$ =
 498 $\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sÄ\8dĂtance volbou
 499 $d=\sqrt{\log L}$ vyrovnĂĄme.
 500
 501 HOT Queue tedy zvlĂĄdne \<Insert> s~amortizovanou Ä\8dasovou sloĹžitostĂ $\O(\sqrt{\log L})$
 502 a ostatnĂ operace v~Ä\8dase amortizovanÄ\9b konstantnĂm. PouĹžijeme-li tuto strukturu
 503 v~DijkstrovÄ\9b algoritmu, spoÄ\8dte vzdĂĄlenosti v~Ä\8dase $\O(m + n\sqrt{\log L})$.
 504
 505 \h{DinicĹŻv algoritmus}
 506
 507 ZajĂmavĂŠ vylepĹĄenĂ Dijkstrova algoritmu navrhl Dinic. VĹĄiml si, Ĺže pokud
 508 je kaĹždĂĄ hrana dlouhĂĄ alespoĹ\88~$\delta$, mĹŻĹžeme uzavĂrat nejen
 509 vrchol s~minimĂĄlnĂm ohodnocenĂm~$\mu$, ale i vĹĄechny s~ohodnocenĂm
 510 menĹĄĂm neĹž $\mu+\delta$.
 511
 512 Pro takto upravenĂ˝ DijkstrĹŻv algoritmus bude stĂĄle platit, Ĺže pĹ\99i uzavĂrĂĄnĂ
 513 vrcholu odpovĂdĂĄ ohodnocenĂ skuteÄ\8dnĂŠ vzdĂĄlenosti, takĹže uzavĹ\99enĂŠ vrcholy jiĹž
 514 nejsou znovu otevĂrĂĄny.
 515
 516 O~monotonii vzdĂĄlenostĂ jsme sice pĹ\99iĹĄli, ale v~pĹ\99ihrĂĄdkovĂŠ struktuĹ\99e nebo
 517 haldÄ\9b mĹŻĹžeme klĂÄ\8de nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
 518 Tyto hodnoty se totiĹž chovajĂ monotĂłnnÄ\9b a vrcholy se stejnĂ˝m $h'(v)$ mĹŻĹžeme
 519 libovolnÄ\9b zamÄ\9bĹ\88ovat.
 520
 521 Kteroukoli z~popsanĂ˝ch pĹ\99ihrĂĄdkovĂ˝ch struktur mĹŻĹžeme tedy pouĹžĂt, pouze
 522 v~rozboru Ä\8dasovĂŠ sloĹžitosti nahradĂme~$L$ vĂ˝razem $L/\delta$. Tento pĹ\99Ăstup
 523 pĹ\99itom funguje i pro neceloÄ\8dĂselnĂŠ dĂŠlky hran, pouze potĹ\99ebujeme mĂt pĹ\99edem
 524 k~dispozici netriviĂĄlnĂ dolnĂ odhad na~vĹĄechny dĂŠlky.
 525
 526 \h{PotenciĂĄly}
 527
 528 VidÄ\9bli jsme, Ĺže v~grafech s~nezĂĄpornĂ˝mi dĂŠlkami hran se nejkratĹĄĂ cesty
 529 hledajĂ snĂĄze. NabĂzĂ se nalĂŠzt nÄ\9bjakou transformaci, kterĂĄ by
 530 dovedla dĂŠlky hran upravit tak, aby byly nejkratĹĄĂ cesty zachovĂĄny (samozĹ\99ejmÄ\9b
 531 ne jejich dĂŠlky, ale alespoĹ\88 to, kterĂŠ cesty jsou nejkratĹĄĂ). NabĂzĂ se
 532 nĂĄsledujĂcĂ fyzikĂĄlnĂ inspirace:
 533
 534 \s{Definice:} {\I PotenciĂĄl} budeme Ĺ\99Ăkat libovolnĂŠ funkci $\psi: V\rightarrow {\bb R}$.
 535 Pro kaĹždĂ˝ potenciĂĄl zavedeme {\I redukovanĂŠ dĂŠlky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
 536 PotenciĂĄl nazveme {\I pĹ\99ĂpustnĂ˝,} pokud ĹžĂĄdnĂĄ hrana nemĂĄ zĂĄpornou redukovanou dĂŠlku.
 537
 538 \s{PozorovĂĄnĂ:} Pro redukovanou dĂŠlku libovolnĂŠ cesty~$P$ z~$u$ do~$v$ platĂ: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.
 539
 540 \proof
 541 NechĹĽ cesta~$P$ prochĂĄzĂ pĹ\99es vrcholy $u=w_1,\ldots,w_k=v$. Potom:
 542 $$
 543 \ell_\psi(P) = \sum_i \ell_\psi(w_i,w_{i+1}) = \sum_i \left( \ell(w_i,w_{i+1}) + \psi(w_i) - \psi(w_{i+1}) \right).
 544 $$
 545 Tato suma je ovĹĄem teleskopickĂĄ, takĹže z~nĂ zbude
 546 $$
 547 \sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k) = \ell(P) + \psi(u) - \psi(v).
 548 $$
 549 \vskip-\baselineskip
 550 \qed
 551
 552 \s{DĹŻsledek:} PotenciĂĄlovou redukcĂ se dĂŠlky vĹĄech cest mezi~$u$ a~$v$
 553 zmÄ\9bnĂ o~tutĂŠĹž konstantu, takĹže struktura nejkratĹĄĂch cest zĹŻstane nezmÄ\9bnÄ\9bna.
 554
 555 ZbĂ˝vĂĄ pĹ\99ijĂt na~to, kde si obstarat nÄ\9bjakĂ˝ pĹ\99ĂpustnĂ˝ potenciĂĄl. PĹ\99idejme do~grafu
 556 novĂ˝ vrchol~$z$, pĹ\99iveÄ\8fme z~nÄ\9bj hrany nulovĂŠ dĂŠlky do~vĹĄech ostatnĂch vrcholĹŻ
 557 a~oznaÄ\8dme~$\psi(v)$ vzdĂĄlenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciĂĄl
 558 pĹ\99ĂpustnĂ˝, musĂ pro kaĹždou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
 559 Tuto nerovnost mĹŻĹžeme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, Ä\8dili
 560 $d(z,u) + \ell(u,v) \ge d(z,v)$, coĹž je ale obyÄ\8dejnĂĄ trojĂşhelnĂkovĂĄ nerovnost
 561 pro vzdĂĄlenost v~grafu, kterĂĄ jistÄ\9b platĂ.
 562
 563 JednĂm vĂ˝poÄ\8dtem nejkratĹĄĂch cest v~grafu se zĂĄpornĂ˝mi hranami (tĹ\99eba algoritmem BFM)
 564 tedy dokĂĄĹžeme spoÄ\8dĂtat potenciĂĄl, kterĂ˝ nĂĄm poslouĹžĂ k~redukci vĹĄech hran na~nezĂĄpornĂŠ
 565 dĂŠlky. To nĂĄm samozĹ\99ejmÄ\9b nepomĹŻĹže, chceme-li jednorĂĄzovÄ\9b hledat nejkratĹĄĂ cestu,
 566 ale mĹŻĹže nĂĄm to vĂ˝raznÄ\9b zjednoduĹĄit dalĹĄĂ, sloĹžitÄ\9bjĹĄĂ prĂĄci s~grafem. Jak uvidĂme
 567 v~pĹ\99ĂĹĄtĂ kapitole, mĹŻĹžeme tak napĹ\99Ăklad nalĂŠzt vzdĂĄlenosti mezi vĹĄemi dvojicemi
 568 vrcholĹŻ v~Ä\8dase $\O(nm + n^2\log n)$.
 569
 570 Na~zĂĄvÄ\9br tohoto oddĂlu dokĂĄĹžeme jedno pomocnĂŠ tvrzenĂ o~potenciĂĄlech, kterĂŠ
 571 nĂĄm pomĹŻĹže v~konstrukci algoritmĹŻ typu \ppsp:
 572
 573 \s{Lemma:} Pokud $f$ a~$g$ jsou pĹ\99ĂpustnĂŠ potenciĂĄly, pak jsou jimi i:
 574 \numlist\ndotted
 575 \:konvexnĂ kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolnĂŠ $\alpha,\beta\ge 0, \alpha+\beta=1$;
 576 \:$\min(f,g)$;
 577 \:$\max(f,g)$.
 578 \endlist
 579
 580 \proof BuÄ\8f $uv$ hrana. Potom z~definice pĹ\99Ăpustnosti platĂ $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$.
 581 JednotlivĂŠ Ä\8dĂĄsti tvrzenĂ dokĂĄĹžeme takto:
 582 \numlist\ndotted
 583 \:Pokud obÄ\9b strany nerovnosti pro~$f$ vynĂĄsobĂme konstantou~$\alpha$, u~nerovnosti pro~$g$
 584   konstantou~$\beta$ a obÄ\9b nerovnosti seÄ\8dteme, dostaneme:
 585   $$
 586   (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)),
 587   $$
 588   coĹž je pĹ\99esnÄ\9b poĹžadovanĂĄ nerovnost pro pĹ\99Ăpustnost funkce $\alpha f+\beta g$.
 589 \:OznaÄ\8dme $h := \min(f,g)$. NechĹĽ bez Ăşjmy na obecnosti $f(u)\le g(u)$. Pokud takĂŠ platĂ $f(v)\le g(v)$,
 590   shoduje se minimum s~funkcĂ~$f$ a nenĂ co dokazovat. V~opaÄ\8dnĂŠm pĹ\99ĂpadÄ\9b je $h(u) = f(u)$, $h(v) = g(v)$.
 591   Tehdy si staÄ\8dĂ vĹĄimnout, Ĺže $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, takĹže
 592   potenciĂĄl~$h$ je pĹ\99ĂpustnĂ˝.
 593 \:DokĂĄĹžeme analogicky.
 594 \qeditem
 595 \endlist
 596
 597 \h{Algoritmy pro problĂŠm typu \ppsp}
 598
 599 ZamÄ\9bĹ\99me se nynĂ na~pĹ\99Ăpad, kdy chceme hledat nejkratĹĄĂ cesty mezi zadanou dvojicĂ
 600 vrcholĹŻ $s$,~$t$. Obvykle se i v~tĂŠto situaci pouĹžĂvajĂ algoritmy \sssp{} (SSSP) a v~obecnĂŠm
 601 pĹ\99ĂpadÄ\9b ani nenĂ efektivnÄ\9bjĹĄĂ Ĺ\99eĹĄenĂ znĂĄmo. Existuje ovĹĄem velkĂŠ mnoĹžstvĂ heuristik, kterĂ˝mi
 602 lze obvykle vĂ˝poÄ\8det zrychlit. NÄ\9bkterĂŠ z~nich si pĹ\99edvedeme na DijkstrovÄ\9b algoritmu.
 603
 604 DijkstrĹŻv algoritmus ve~svĂŠ klasickĂŠ podobÄ\9b nevĂ vĹŻbec nic o~cĂlovĂŠm vrcholu a
 605 prohledĂĄ celĂ˝ graf. Hned se nabĂzĂ vyuĹžĂt toho, Ĺže od~okamĹžiku uzavĹ\99enĂ
 606 kterĂŠhokoliv vrcholu se jiĹž jeho ohodnocenĂ nezmÄ\9bnĂ. Pokud tedy uzavĹ\99eme cĂlovĂ˝
 607 vrchol, mĹŻĹžeme se zastavit.
 608
 609 Jakou Ä\8dĂĄst grafu prohledĂĄvĂĄme teÄ\8f? V~metrice danĂŠ vzdĂĄlenostmi v~grafu je to nejmenĹĄĂ
 610 koule se stĹ\99edem ve~vrcholu~$u$, kterĂĄ obsahuje nejkratĹĄĂ cestu (dobĹ\99e se to
 611 pĹ\99edstavuje na~hledĂĄnĂ v~silniÄ\8dnĂ sĂti na~rovinnĂŠ mapÄ\9b).
 612
 613 TakĂŠ mĹŻĹžeme spustit prohledĂĄvĂĄnĂ z~obou koncĹŻ zĂĄroveĹ\88, tedy zkombinovat hledĂĄnĂ
 614 od~$s$ v~pĹŻvodnĂm grafu s~hledĂĄnĂm od~$t$ v~grafu s~obrĂĄcenou orientacĂ hran.
 615 Oba postupy mĹŻĹžeme libovolnÄ\9b stĹ\99Ădat a zastavĂme se v~okamĹžiku, kdy jsme jeden
 616 vrchol uzavĹ\99eli v~obou smÄ\9brech. Pozor ovĹĄem na to, Ĺže souÄ\8det obou ohodnocenĂ
 617 tohoto vrcholu nemusĂ bĂ˝t roven $d(v,u)$ -- zkuste vymyslet protipĹ\99Ăklad.
 618 NejkratĹĄĂ cesta jeĹĄtÄ\9b mĹŻĹže vypadat tak, Ĺže pĹ\99echĂĄzĂ po nÄ\9bjakĂŠ hranÄ\9b mezi vrcholem
 619 uzavĹ\99enĂ˝m v~jednom smÄ\9bru a vrcholem uzavĹ\99enĂ˝m ve~smÄ\9bru druhĂŠm (ponechme bez dĹŻkazu).
 620 StaÄ\8dĂ tedy bÄ\9bhem relaxace zjistit, zda je konec hrany uzavĹ\99enĂ˝ v~opaÄ\8dnĂŠm
 621 smÄ\9bru prohledĂĄvĂĄnĂ, a~pokud ano, zapoÄ\8dĂtat cestu do~prĹŻbÄ\9bĹžnĂŠho minima.
 622
 623 ObousmÄ\9brnĂ˝ DijkstrĹŻv algoritmus projde sjednocenĂ nÄ\9bjakĂŠ koule okolo~$s$ s~nÄ\9bjakou
 624 koulĂ okolo~$t$, kterĂŠ obsahuje nejkratĹĄĂ cestu. PrĹŻmÄ\9bry koulĂ pĹ\99itom zĂĄvisĂ na tom,
 625 jak budeme bÄ\9bhem vĂ˝poÄ\8dtu stĹ\99Ădat oba smÄ\9bry prohledĂĄvĂĄnĂ. V~nejhorĹĄĂm pĹ\99ĂpadÄ\9b samozĹ\99ejmÄ\9b
 626 mĹŻĹžeme prohledat celĂ˝ graf.
 627
 628 \h{Algoritmus \astar}
 629
 630 V~umÄ\9blĂŠ inteligenci se Ä\8dasto pro hledĂĄnĂ nejkratĹĄĂ cesty v~rozsĂĄhlĂ˝ch grafech
 631 (obvykle stavovĂ˝ch prostorech Ăşloh) pouĹžĂvĂĄ algoritmus nazĂ˝vanĂ˝~\astar{} \cite{hart:astar}.
 632 JednĂĄ se o~modifikaci Dijkstrova algoritmu, kterĂĄ vyuĹžĂvĂĄ heuristickou funkci
 633 pro dolnĂ odhad vzdĂĄlenosti do~cĂle; oznaÄ\8dme si ji $\psi(v)$. V~kaĹždĂŠm kroku pak uzavĂra
 634 vrchol~$v$ s~nejmenĹĄĂm moĹžnĂ˝m souÄ\8dtem $h(v)+\psi(v)$ aktuĂĄlnĂho ohodnocenĂ s~heuristikou.
 635
 636 Intuice za tĂmto algoritmem je jasnĂĄ: pokud vĂme, Ĺže nÄ\9bjakĂ˝ vrchol je blĂzko
 637 od~poÄ\8dĂĄtaÄ\8dnĂho vrcholu~$s$, ale bude z~nÄ\9bj urÄ\8ditÄ\9b daleko do cĂle~$t$, zatĂm ho
 638 odloĹžĂme a budeme zkoumat nadÄ\9bjnÄ\9bjĹĄĂ varianty.
 639
 640 Heuristika se pĹ\99itom volĂ podle konkrĂŠtnĂho problĂŠmu -- napĹ\99. hledĂĄme-li cestu
 641 v~mapÄ\9b, mĹŻĹžeme pouĹžĂt vzdĂĄlenost do~cĂle vzduĹĄnou Ä\8darou.
 642
 643 Je u~tohoto algoritmu zaruÄ\8deno, Ĺže vĹždy najde nejkratĹĄĂ cestu? Na to nĂĄm dĂĄ odpovÄ\9bÄ\8f
 644 teorie potenciĂĄlĹŻ:
 645
 646 \s{VÄ\9bta:} BÄ\9bh algoritmu \astar{} odpovĂdĂĄ prĹŻbÄ\9bhu Dijkstrova algoritmu
 647 na~grafu redukovanĂŠm potenciĂĄlem~$-\psi$. PĹ\99esnÄ\9bji,
 648 pokud oznaÄ\8dĂme $h^*$ aktuĂĄlnĂ ohodnocenĂ v~\astar{} a $h$ aktuĂĄlnĂ ohodnocenĂ
 649 v~synchronnÄ\9b bÄ\9bĹžĂcĂm Dijkstrovi, bude vĹždy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
 650
 651 \proof
 652 IndukcĂ podle doby bÄ\9bhu obou algoritmĹŻ. Na poÄ\8dĂĄtku je $h^*(s)$ i $h(s)$ nulovĂŠ
 653 a vĹĄechna ostatnĂ $h^*$ a~$h$ jsou nekoneÄ\8dnĂĄ, takĹže tvrzenĂ platĂ. V~kaĹždĂŠm dalĹĄĂm
 654 kroku \astar{} vybere vrchol~$v$ s~nejmenĹĄĂm $h^*(v) + \psi(v)$, coĹž je tentĂ˝Ĺž vrchol,
 655 kterĂ˝ vybere Dijkstra ($\psi(s)$ je stĂĄle stejnĂŠ).
 656
 657 UvaĹžujme, co se stane bÄ\9bhem relaxace hrany $vw$: Dijkstra se pokusĂ snĂĹžit ohodnocenĂ $h(w)$
 658 o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. UkĂĄĹžeme,
 659 Ĺže \astar{} udÄ\9blĂĄ totĂŠĹž:
 660 $$\eqalign{
 661 \delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
 662 &= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
 663 &= h^*(w) - h^*(v) - \ell(v,w).
 664 }$$
 665 Oba algoritmy tedy aĹž na~posunutĂ danĂŠ potenciĂĄlem poÄ\8dĂtajĂ totĂŠĹž.
 666 \qed
 667
 668 \s{DĹŻsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciĂĄl $-\psi$ pĹ\99ĂpustnĂ˝.
 669
 670 NapĹ\99Ăklad pro rovinnou mapu to heuristika danĂĄ euklidovskou vzdĂĄlenostĂ~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splĹ\88uje:
 671 PĹ\99Ăpustnost poĹžaduje pro kaĹždou hranu $uv$ nerovnost
 672 $\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
 673 tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
 674 JelikoĹž $\ell(u,v) \ge \varrho(u,v)$,
 675 staÄ\8dĂ dokĂĄzat, Ĺže $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
 676 coĹž je ovĹĄem trojĂşhelnĂkovĂĄ nerovnost pro metriku~$\varrho$.
 677
 678 \references
 679 \bye