From e6c6d5cc41cf563dcd52dbca2f20dbdd82510374 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 27 Nov 2017 15:16:32 +0100
Subject: [PATCH] =?utf8?q?Dijkstra:=20Oprava=20scestn=C3=A9ho=20p=C5=99ek?=
 =?utf8?q?=C3=B3dov=C3=A1n=C3=AD?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 13-dijkstra/13-dijkstra.tex | 1002 +++++++++++++++++------------------
 1 file changed, 501 insertions(+), 501 deletions(-)

diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex
index 48b28a4..942839d 100644
--- a/13-dijkstra/13-dijkstra.tex
+++ b/13-dijkstra/13-dijkstra.tex
@@ -1,679 +1,679 @@
 \input ../sgr.tex
 
-\prednaska{13}{NejkratĹĄĂ­ cesty}{}
+\prednaska{13}{Nejkratší cesty}{}
 
 \def\ppsp{1-1}
 \def\sssp{1-$n$}
 \def\apsp{$n$-$n$}
 \def\astar{A\kern-0.15em *}
 
-ProblĂŠm hledĂĄnĂ­ nejkratĹĄĂ­ cesty v~(obvykle ohodnocenĂŠm orientovanĂŠm) grafu
-provází teorii grafových algoritmů od~samých počátků. Základní algoritmy
-pro hledání cest jsou nedílnou součástí základních kursů programování
-a algoritmů, my se budeme věnovat zejména různým jejich vylepšením.
+Problém hledání nejkratší cesty v~(obvykle ohodnoceném orientovaném) grafu
+provází teorii grafových algoritmů od~samých počátků. Základní algoritmy
+pro hledání cest jsou nedílnou součástí základních kursů programování
+a algoritmů, my se budeme věnovat zejména různým jejich vylepšením.
 
-Uvažujme tedy nějaký orientovaný graf, jehož každá hrana~$e$ je opatřena
-{\I délkou} $\ell(e)\in{\bb R}$. Množině hran (třeba sledu nebo cestě)
-pak přiřadíme délku rovnou součtu délek jednotlivých hran.
+Uvažujme tedy nějaký orientovaný graf, jehož každá hrana~$e$ je opatřena
+{\I délkou} $\ell(e)\in{\bb R}$. Množině hran (třeba sledu nebo cestě)
+pak přiřadíme délku rovnou součtu délek jednotlivých hran.
 
-Pro vrcholy $u,v$ definujeme jejich {\I vzdĂĄlenost} $d(u,v)$ jako nejmenĹĄĂ­
-možnou délku cesty z~$u$ do~$v$ (jelikož cest je v~grafu konečně mnoho,
-minimum vŞdy existuje). Pokud z~$u$ do~$v$ Şådnå cesta nevede, poloŞíme
+Pro vrcholy $u,v$ definujeme jejich {\I vzdálenost} $d(u,v)$ jako nejmenší
+možnou délku cesty z~$u$ do~$v$ (jelikož cest je v~grafu konečně mnoho,
+minimum vždy existuje). Pokud z~$u$ do~$v$ žádná cesta nevede, položíme
 $d(u,v) := \infty$.
 
-Obvykle se studují následující tři problémy:
+Obvykle se studují následující tři problémy:
 
 \itemize\ibull
-\:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalĂŠzt nejkratĹĄĂ­
-  cestu z~danĂŠho vrcholu~$u$ do~danĂŠho vrcholu~$v$. (Pokud je nejkratĹĄĂ­ch cest
-  vĂ­ce, tak libovolnou z~nich.)
-\:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro danĂ˝ vrchol~$u$ chceme
-  nalĂŠzt nejkratĹĄĂ­ cesty do~vĹĄech ostatnĂ­ch vrcholĹŻ.
-\:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajĂ­majĂ­ nĂĄs nejkratĹĄĂ­ cesty
-  mezi vĹĄemi dvojicemi vrcholĹŻ.
+\:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkratší
+  cestu z~daného vrcholu~$u$ do~daného vrcholu~$v$. (Pokud je nejkratších cest
+  více, tak libovolnou z~nich.)
+\:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
+  nalézt nejkratší cesty do~všech ostatních vrcholů.
+\:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkratší cesty
+  mezi všemi dvojicemi vrcholů.
 \endlist
 
-Překvapivě, tak obecně, jak jsme si uvedené problémy definovali, je neumíme
-řešit v~polynomiálním čase: pro grafy, které mohou obsahovat hrany záporných
-délek bez jakýchkoliv omezení, je totiž hledání nejkratší cesty NP-těžké
-(lze na~něj snadno převést existenci hamiltonovské cesty). Všechny známé
-polynomiĂĄlnĂ­ algoritmy totiĹž mĂ­sto nejkratĹĄĂ­ cesty hledajĂ­ nejkratĹĄĂ­ sled
--- nijak nekontrolujĂ­, zda cesta neprojde jednĂ­m vrcholem vĂ­cekrĂĄt.
-
-Naštěstí pro nás je to v~grafech bez cyklů záporné délky totéž: pokud se
-v~nalezeném sledu vyskytne cyklus, můžeme jej \uv{vystřihnout} a tím získat
-sled, který není delší a~který má méně hran. Každý nejkratší sled tak
-můžeme upravit na~stejně dlouhou cestu.
-V~grafech bez zåporných cyklů je tedy jedno, zda hledåme sled nebo cestu;
-naopak vyskytne-li se záporný cyklus dosažitelný z~počátečního vrcholu,
-nejkratĹĄĂ­ sled ani neexistuje.
-
-Navíc se nám bude hodit, že každý prefix nejkratší cesty je opět nejkratší
-cesta. Jinými slovy pokud některá z~nejkratších cest z~$u$ do~$v$ vede
-přes nějaký vrchol~$w$, pak její část z~$u$ do~$w$ je jednou z~nejkratších
-cest z~$u$ do~$w$. (V~opačném případě bychom mohli úsek $u\ldots w$ vyměnit za~kratší.)
-
-DĂ­ky tĂŠto {\I prefixovĂŠ vlastnosti} mĹŻĹžeme pro kaĹždĂ˝ vrchol~$u$ sestrojit jeho {\I strom
-nejkratších cest}~${\cal T}(u)$. To je nějaký podgraf grafu~$G$, který má tvar
-stromu zakořeněného v~$u$ a orientovaného směrem od~kořene, a~platí pro něj, že
-pro kaĹždĂ˝ vrchol~$v$ je (jedinĂĄ) cesta z~$u$ do~$v$ v~tomto stromu jednou
-z~nejkratĹĄĂ­ch cest z~$u$ do~$v$ v~pĹŻvodnĂ­m grafu.
-
-\s{PozorovĂĄnĂ­:} Strom nejkratĹĄĂ­ch cest vĹždy existuje.
+Překvapivě, tak obecně, jak jsme si uvedené problémy definovali, je neumíme
+řešit v~polynomiálním čase: pro grafy, které mohou obsahovat hrany záporných
+délek bez jakýchkoliv omezení, je totiž hledání nejkratší cesty NP-těžké
+(lze na~něj snadno převést existenci hamiltonovské cesty). Všechny známé
+polynomiální algoritmy totiž místo nejkratší cesty hledají nejkratší sled
+-- nijak nekontrolují, zda cesta neprojde jedním vrcholem vícekrát.
+
+Naštěstí pro nás je to v~grafech bez cyklů záporné délky totéž: pokud se
+v~nalezeném sledu vyskytne cyklus, můžeme jej \uv{vystřihnout} a tím získat
+sled, který není delší a~který má méně hran. Každý nejkratší sled tak
+můžeme upravit na~stejně dlouhou cestu.
+V~grafech bez záporných cyklů je tedy jedno, zda hledáme sled nebo cestu;
+naopak vyskytne-li se záporný cyklus dosažitelný z~počátečního vrcholu,
+nejkratší sled ani neexistuje.
+
+Navíc se nám bude hodit, že každý prefix nejkratší cesty je opět nejkratší
+cesta. Jinými slovy pokud některá z~nejkratších cest z~$u$ do~$v$ vede
+přes nějaký vrchol~$w$, pak její část z~$u$ do~$w$ je jednou z~nejkratších
+cest z~$u$ do~$w$. (V~opačném případě bychom mohli úsek $u\ldots w$ vyměnit za~kratší.)
+
+Díky této {\I prefixové vlastnosti} můžeme pro každý vrchol~$u$ sestrojit jeho {\I strom
+nejkratších cest}~${\cal T}(u)$. To je nějaký podgraf grafu~$G$, který má tvar
+stromu zakořeněného v~$u$ a orientovaného směrem od~kořene, a~platí pro něj, že
+pro každý vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou
+z~nejkratších cest z~$u$ do~$v$ v~původním grafu.
+
+\s{Pozorování:} Strom nejkratších cest vždy existuje.
 
 \proof
-NechĹĽ $u=v_1,\ldots,v_n$ jsou vĹĄechny vrcholy grafu~$G$. IndukcĂ­ budeme
-dokazovat, že pro každé~$i$ existuje strom~${\cal T}_i$, v~němž se nacházejí nejkratší
-cesty z~vrcholu~$u$ do vrcholů $v_1,\ldots,v_i$. Pro $i=1$ stačí uvážit
-strom obsahujĂ­cĂ­ jedinĂ˝ vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobĂ­me
-strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkratĹĄĂ­ cestu z~$u$ do~$v_i$
-a označíme~$z$ poslední vrchol na~této cestě, který se ještě vyskytuje v~${\cal T}_{i-1}$.
-Úsek nejkratší cesty od~$z$ do~$v_i$ pak přidáme do~${\cal T}_{i-1}$
-a dĂ­ky prefixovĂŠ vlastnosti bude i cesta z~$u$ do~$v_i$ v~novĂŠm stromu
-nejkratĹĄĂ­.
+Nechť $u=v_1,\ldots,v_n$ jsou všechny vrcholy grafu~$G$. Indukcí budeme
+dokazovat, že pro každé~$i$ existuje strom~${\cal T}_i$, v~němž se nacházejí nejkratší
+cesty z~vrcholu~$u$ do vrcholů $v_1,\ldots,v_i$. Pro $i=1$ stačí uvážit
+strom obsahující jediný vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
+strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkratší cestu z~$u$ do~$v_i$
+a označíme~$z$ poslední vrchol na~této cestě, který se ještě vyskytuje v~${\cal T}_{i-1}$.
+Úsek nejkratší cesty od~$z$ do~$v_i$ pak přidáme do~${\cal T}_{i-1}$
+a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
+nejkratší.
 \qed
 
-Zbývå se dohodnout, v~jakÊm tvaru mají naťe algoritmy vydåvat výsledek.
-U~problÊmů typu \ppsp{} je nejjednoduťťí vypsat celou cestu, u~\sssp{} můŞeme jako výstup
-vydat strom nejkratších cest z~daného počátku (všimněte si, že stačí
-uvést předchůdce každého vrcholu), u~\apsp{} vydáme strom nejkratších cest
-pro kaŞdý ze~zdrojových vrcholů.
+Zbývá se dohodnout, v~jakém tvaru mají naše algoritmy vydávat výsledek.
+U~problémů typu \ppsp{} je nejjednodušší vypsat celou cestu, u~\sssp{} můžeme jako výstup
+vydat strom nejkratších cest z~daného počátku (všimněte si, že stačí
+uvést předchůdce každého vrcholu), u~\apsp{} vydáme strom nejkratších cest
+pro každý ze~zdrojových vrcholů.
 
-Často se ovšem ukáže, že podstatná část problému se skrývá v~samotném
-výpočtu vzdáleností a sestrojení předchůdců je triviálním rozšířením algoritmu.
-Budeme tedy obvykle jen počítat vzdálenosti a samotnou rekonstrukci cest
-ponecháme čtenáři jako snadné cvičení.
+Často se ovšem ukáže, že podstatná část problému se skrývá v~samotném
+výpočtu vzdáleností a sestrojení předchůdců je triviálním rozšířením algoritmu.
+Budeme tedy obvykle jen počítat vzdálenosti a samotnou rekonstrukci cest
+ponecháme čtenáři jako snadné cvičení.
 
-\h{Relaxační algoritmus}
+\h{Relaxační algoritmus}
 
-Začněme problémem \sssp{} a označme~$u$ výchozí vrchol. Většina známých
-algoritmĹŻ funguje tak, Ĺže pro kaĹždĂ˝ vrchol~$v$ udrĹžujĂ­ ohodnocenĂ­ $h(v)$,
-které v~každém okamžiku odpovídá délce nějakého sledu z~$u$ do~$v$. Postupně
-toto ohodnocení upravují, až se z~něj stane vzdálenost $d(u,v)$ a algoritmus
-se mĹŻĹže zastavit.
+Začněme problémem \sssp{} a označme~$u$ výchozí vrchol. Většina známých
+algoritmů funguje tak, že pro každý vrchol~$v$ udržují ohodnocení $h(v)$,
+které v~každém okamžiku odpovídá délce nějakého sledu z~$u$ do~$v$. Postupně
+toto ohodnocení upravují, až se z~něj stane vzdálenost $d(u,v)$ a algoritmus
+se může zastavit.
 
-Vhodnou operacĂ­ pro vylepĹĄovĂĄnĂ­ ohodnocenĂ­ je takzvanĂĄ {\I relaxace.}
-Vybereme si nějaký vrchol~$v$ a pro všechny jeho sousedy~$w$ spočítáme
-$h(v) + \ell(v,w)$, tedy délku sledu, který vznikne rozšířením aktuálního
-sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota menĹĄĂ­ neĹž~$h(w)$,
-tak jí $h(w)$ přepíšeme.
+Vhodnou operací pro vylepšování ohodnocení je takzvaná {\I relaxace.}
+Vybereme si nějaký vrchol~$v$ a pro všechny jeho sousedy~$w$ spočítáme
+$h(v) + \ell(v,w)$, tedy délku sledu, který vznikne rozšířením aktuálního
+sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota menší než~$h(w)$,
+tak jí $h(w)$ přepíšeme.
 
-Abychom zabránili opakovaným relaxacím téhož vrcholu, které nic nezmění,
-budeme rozlišovat tři stavy vrcholů: {\I neviděn} (ještě jsme ho nenavštívili),
-{\I otevřen} (změnilo se ohodnocení, časem chceme relaxovat) a {\I uzavřen}
-(už jsme relaxovali a není potřeba znovu).
+Abychom zabránili opakovaným relaxacím téhož vrcholu, které nic nezmění,
+budeme rozlišovat tři stavy vrcholů: {\I neviděn} (ještě jsme ho nenavštívili),
+{\I otevřen} (změnilo se ohodnocení, časem chceme relaxovat) a {\I uzavřen}
+(už jsme relaxovali a není potřeba znovu).
 
-Náš algoritmus bude fungovat následovně:
+Náš algoritmus bude fungovat následovně:
 
 \algo
 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
-\:$\<stav>(*)\leftarrow\<neviděn>$, $\<stav>(u)\leftarrow\<otevřen>$.
-\:Dokud existují otevřené vrcholy, opakujeme:
-\::$v\leftarrow\hbox{libovolný otevřený vrchol}$.
-\::$\<stav>(v)\leftarrow\<uzavřen>$.
+\:$\<stav>(*)\leftarrow\<neviděn>$, $\<stav>(u)\leftarrow\<otevřen>$.
+\:Dokud existují otevřené vrcholy, opakujeme:
+\::$v\leftarrow\hbox{libovolný otevřený vrchol}$.
+\::$\<stav>(v)\leftarrow\<uzavřen>$.
 \::Relaxujeme~$v$:
-\:::Pro vĹĄechny hrany $vw$ opakujeme:
+\:::Pro všechny hrany $vw$ opakujeme:
 \::::Je-li $h(w) > h(v) + \ell(v,w)$:
 \:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
-\:::::$\<stav>(w)\leftarrow\<otevřen>$.
-\:Vråtíme výsledek $d(u,v)=h(v)$ pro vťechna~$v$.
+\:::::$\<stav>(w)\leftarrow\<otevřen>$.
+\:Vrátíme výsledek $d(u,v)=h(v)$ pro všechna~$v$.
 \endalgo
 
-Podobně jako u~minimálních koster, i zde se jedná o~meta-algoritmus, protože
-v~kroku~4 nespecifikuje, který z~otevřených vrcholů vybírá. Přesto
-ale můžeme dokázat několik zajímavých tvrzení, která na~konkrétním způsobu
-výběru nezávisejí.
+Podobně jako u~minimálních koster, i zde se jedná o~meta-algoritmus, protože
+v~kroku~4 nespecifikuje, který z~otevřených vrcholů vybírá. Přesto
+ale můžeme dokázat několik zajímavých tvrzení, která na~konkrétním způsobu
+výběru nezávisejí.
 
-\s{Věta:} Spustíme-li meta-algoritmus na graf bez záporných cyklů, pak:
+\s{Věta:} Spustíme-li meta-algoritmus na graf bez záporných cyklů, pak:
 
 \numlist\nparen
-\:Ohodnocení $h(v)$ vždy odpovídá délce nějakého sledu z~$u$ do~$v$.
-\:$h(v)$ dokonce odpovídá délce nějaké cesty z~$u$ do~$v$.
-\:Algoritmus se vĹždy zastavĂ­.
-\:Po zastavení jsou označeny jako uzavřené právě ty vrcholy, které jsou dosažitelné z~$u$.
-\:Po zastavení mají konečné~$h(v)$ právě všechny uzavřené vrcholy.
-\:Pro kaĹždĂ˝ dosaĹžitelnĂ˝ vrchol je na~konci $h(v)$ rovno $d(u,v)$.
+\:Ohodnocení $h(v)$ vždy odpovídá délce nějakého sledu z~$u$ do~$v$.
+\:$h(v)$ dokonce odpovídá délce nějaké cesty z~$u$ do~$v$.
+\:Algoritmus se vždy zastaví.
+\:Po zastavení jsou označeny jako uzavřené právě ty vrcholy, které jsou dosažitelné z~$u$.
+\:Po zastavení mají konečné~$h(v)$ právě všechny uzavřené vrcholy.
+\:Pro každý dosažitelný vrchol je na~konci $h(v)$ rovno $d(u,v)$.
 \endlist
 
 \proof
 
 \numlist\nparen
-\:Dokážeme indukcí podle počtu kroků algoritmu.
-\:Stačí rozmyslet, v~jaké situaci by vytvořený sled mohl obsahovat cyklus.
-\:Cest, a~tím pádem i možných hodnot~$h(v)$ pro každý~$v$, je konečně mnoho.
-\:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ stačí uvážit neuzavřený vrchol,
-  který je dosažitelný z~$u$ cestou o~co nejmenším počtu hran.
-\:$h(v)$ nastavujeme na~konečnou hodnotu právě v~okamžicích, kdy se vrchol stává otevřeným.
-  Každý otevřený vrchol je časem uzavřen.
+\:Dokážeme indukcí podle počtu kroků algoritmu.
+\:Stačí rozmyslet, v~jaké situaci by vytvořený sled mohl obsahovat cyklus.
+\:Cest, a~tím pádem i možných hodnot~$h(v)$ pro každý~$v$, je konečně mnoho.
+\:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ stačí uvážit neuzavřený vrchol,
+  který je dosažitelný z~$u$ cestou o~co nejmenším počtu hran.
+\:$h(v)$ nastavujeme na~konečnou hodnotu právě v~okamžicích, kdy se vrchol stává otevřeným.
+  Každý otevřený vrchol je časem uzavřen.
 \:Kdyby tomu tak nebylo,
-  vyberme si ze~\uv{špatných} vrcholů~$v$ takový, pro nějž obsahuje nejkratší cesta z~$u$ do~$v$
-  nejmenší možný počet hran. Vrchol~$v$ je zajisté různý od~$u$, takže má na~této cestě nějakého
-  předchůdce~$w$. Přitom~$w$ už musí být ohodnocen správně a relaxace, která mu toto ohodnocení
-  nastavila, ho musela prohlásit za~otevřený. Jenže každý otevřený vrchol je později uzavřen,
-  takže~$w$ poté musel být ještě alespoň jednou relaxován, což muselo snížit~$h(v)$ na správnou
-  vzdĂĄlenost.
+  vyberme si ze~\uv{špatných} vrcholů~$v$ takový, pro nějž obsahuje nejkratší cesta z~$u$ do~$v$
+  nejmenší možný počet hran. Vrchol~$v$ je zajisté různý od~$u$, takže má na~této cestě nějakého
+  předchůdce~$w$. Přitom~$w$ už musí být ohodnocen správně a relaxace, která mu toto ohodnocení
+  nastavila, ho musela prohlásit za~otevřený. Jenže každý otevřený vrchol je později uzavřen,
+  takže~$w$ poté musel být ještě alespoň jednou relaxován, což muselo snížit~$h(v)$ na správnou
+  vzdálenost.
 \qeditem
 \endlist
 
-\>DokĂĄzali jsme tedy, Ĺže meta-algoritmus pro libovolnou implementaci kroku~4
-spočítá správné vzdálenosti.
+\>Dokázali jsme tedy, že meta-algoritmus pro libovolnou implementaci kroku~4
+spočítá správné vzdálenosti.
 
 \medskip
 
-\s{Cvičení:}
+\s{Cvičení:}
 \itemize\ibull
-\:Nechť do algoritmu doplníme udržování předchůdců tak, že v~kroku~9
-  přenastavíme předchůdce vrcholu~$w$ na vrchol~$v$. Dokažte, že předchůdci
-  dosažitelných vrcholů budou tvořit strom a že tento strom bude stromem
-  nejkratĹĄĂ­ch cest z~vrcholu~$u$.
-\:Dokažte, že pro graf, v~němž je alespoň jeden záporný cyklus dosažitelný
-  z~počátečního vrcholu, se algoritmus nezastaví a ohodnocení všech vrcholů
-  na cyklu postupně klesnou libovolně hluboko. Nedosažitelné záporné cykly
-  chod algoritmu samozřejmě nijak neovlivní.
+\:Nechť do algoritmu doplníme udržování předchůdců tak, že v~kroku~9
+  přenastavíme předchůdce vrcholu~$w$ na vrchol~$v$. Dokažte, že předchůdci
+  dosažitelných vrcholů budou tvořit strom a že tento strom bude stromem
+  nejkratších cest z~vrcholu~$u$.
+\:Dokažte, že pro graf, v~němž je alespoň jeden záporný cyklus dosažitelný
+  z~počátečního vrcholu, se algoritmus nezastaví a ohodnocení všech vrcholů
+  na cyklu postupně klesnou libovolně hluboko. Nedosažitelné záporné cykly
+  chod algoritmu samozřejmě nijak neovlivní.
 \endlist
 
-\h{BellmanĹŻv-FordĹŻv-MooreĹŻv algoritmus}
+\h{Bellmanův-Fordův-Mooreův algoritmus}
 
-Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobě algoritmus (říkejme mu BFM),
-který lze v~řeči našeho meta-algoritmu formulovat takto: Otevřené vrcholy
-udržujeme ve~frontě (vždy relaxujeme vrchol na počátku fronty, nově otevírané
-zařazujeme na~konec). Co toto pravidlo způsobí?
+Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobě algoritmus (říkejme mu BFM),
+který lze v~řeči našeho meta-algoritmu formulovat takto: Otevřené vrcholy
+udržujeme ve~frontě (vždy relaxujeme vrchol na počátku fronty, nově otevírané
+zařazujeme na~konec). Co toto pravidlo způsobí?
 
-\s{Věta:} Časová složitost algoritmu~BFM činí $\O(nm)$.
+\s{Věta:} Časová složitost algoritmu~BFM činí $\O(nm)$.
 
 \proof
-Běh algoritmu rozdělíme na~fáze. Nultá fáze sestává z~vložení vrcholu~$u$
-do~fronty. V~$(i+1)$-nĂ­ fĂĄzi relaxujeme ty vrcholy, kterĂŠ byly do~fronty
-uloženy během $i$-té fáze.
-
-Jelikož relaxace vrcholu trvá lineárně se stupněm vrcholu a každý vrchol
-se dané fáze účastní nejvýše jednou, trvá jedna fáze $\O(m)$. Zbývá ukázat,
-Şe fåzí provedeme nejvýťe~$n$.
-
-IndukcĂ­ dokĂĄĹžeme, Ĺže na konci $i$-tĂŠ fĂĄze je kaĹždĂŠ ohodnocenĂ­ $h(v)$ shora omezeno
-délkou nejkratšího z~$uv$-sledů o~nejvýše~$i$ hranách. Pro $i=0$ to triviálně
-platí. Uvažujme nyní vrchol~$v$ na konci $(i+1)$-ní fáze a nějaký nejkratší $uv$-sled~$P$
-o~$i+1$ hranách. Označme $wv$ poslední hranu tohoto sledu a $P'$ sled bez této hrany,
-který tedy má délku~$i$. Podle indukčního předpokladu je na konci $i$-té fáze
-$h(w)\le \ell(P')$. Tuto hodnotu získalo $h(w)$ nejpozději v~$i$-té fázi, při tom jsme
-vrchol~$w$ otevřeli, takže jsme ho nejpozději v~$(i+1)$-ní fázi zavřeli a relaxovali.
-Po tĂŠto relaxaci je ovĹĄem $h(v)\le h(w)+\ell(w,v)\le \ell(P') + \ell(w,v) = \ell(P)$.
+Běh algoritmu rozdělíme na~fáze. Nultá fáze sestává z~vložení vrcholu~$u$
+do~fronty. V~$(i+1)$-ní fázi relaxujeme ty vrcholy, které byly do~fronty
+uloženy během $i$-té fáze.
+
+Jelikož relaxace vrcholu trvá lineárně se stupněm vrcholu a každý vrchol
+se dané fáze účastní nejvýše jednou, trvá jedna fáze $\O(m)$. Zbývá ukázat,
+že fází provedeme nejvýše~$n$.
+
+Indukcí dokážeme, že na konci $i$-té fáze je každé ohodnocení $h(v)$ shora omezeno
+délkou nejkratšího z~$uv$-sledů o~nejvýše~$i$ hranách. Pro $i=0$ to triviálně
+platí. Uvažujme nyní vrchol~$v$ na konci $(i+1)$-ní fáze a nějaký nejkratší $uv$-sled~$P$
+o~$i+1$ hranách. Označme $wv$ poslední hranu tohoto sledu a $P'$ sled bez této hrany,
+který tedy má délku~$i$. Podle indukčního předpokladu je na konci $i$-té fáze
+$h(w)\le \ell(P')$. Tuto hodnotu získalo $h(w)$ nejpozději v~$i$-té fázi, při tom jsme
+vrchol~$w$ otevřeli, takže jsme ho nejpozději v~$(i+1)$-ní fázi zavřeli a relaxovali.
+Po této relaxaci je ovšem $h(v)\le h(w)+\ell(w,v)\le \ell(P') + \ell(w,v) = \ell(P)$.
 \qed
 
-\s{Cvičení:}
+\s{Cvičení:}
 \itemize\ibull
-\:Ukažte, že asymptoticky stejné časové složitosti by dosáhl algoritmus,
-  který by vrcholy očísloval $v_1,\ldots,v_n$ a opakovaně by je v~tomto
-  pořadí relaxoval tak dlouho, dokud by se ohodnocení měnila.
-\:Jak algoritmus upravit, aby v~$i$-té fázi spočítal minimální délky sledů
-  o~právě~$i$ hranách?
-\:Jak lze algoritmus BFM vyuŞít k~nalezení zåpornÊho cyklu?
+\:Ukažte, že asymptoticky stejné časové složitosti by dosáhl algoritmus,
+  který by vrcholy očísloval $v_1,\ldots,v_n$ a opakovaně by je v~tomto
+  pořadí relaxoval tak dlouho, dokud by se ohodnocení měnila.
+\:Jak algoritmus upravit, aby v~$i$-té fázi spočítal minimální délky sledů
+  o~právě~$i$ hranách?
+\:Jak lze algoritmus BFM využít k~nalezení záporného cyklu?
 \endlist
 
-\h{DijkstrĹŻv algoritmus}
+\h{Dijkstrův algoritmus}
 
-Pokud jsou všechny délky hran nezáporné, můžeme použít efektivnější pravidlo
-pro výběr vrcholu navržené Dijkstrou \cite{dijkstra:mstandpath}. To říká, že vždy relaxujeme ten z~otevřených
-vrcholĹŻ, jehoĹž ohodnocenĂ­ je nejmenĹĄĂ­.
+Pokud jsou všechny délky hran nezáporné, můžeme použít efektivnější pravidlo
+pro výběr vrcholu navržené Dijkstrou \cite{dijkstra:mstandpath}. To říká, že vždy relaxujeme ten z~otevřených
+vrcholů, jehož ohodnocení je nejmenší.
 
-\s{Věta:} Dijkstrův algoritmus uzavírá vrcholy v~pořadí podle neklesající
-vzdálenosti od~$u$ a každý dosažitelný vrchol uzavře právě jednou.
+\s{Věta:} Dijkstrův algoritmus uzavírá vrcholy v~pořadí podle neklesající
+vzdálenosti od~$u$ a každý dosažitelný vrchol uzavře právě jednou.
 
 \proof
-Indukcí dokážeme, že v~každém okamžiku mají všechny uzavřené vrcholy ohodnocení
-menší nebo rovné ohodnocením všech otevřených vrcholů. Na~počátku to jistě platí.
-Nechť nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevřenými. Během jeho
-relaxace nemůŞeme Şådnou hodnotu sníŞit pod~$h(v)$, jelikoŞ v~grafu s~nezåpornými
-hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevřených vrcholů
-tedy neklesne pod hodnotu tohoto nově uzavřeného. Hodnoty dříve uzavřených vrcholů
-se nemohou nijak změnit.
+Indukcí dokážeme, že v~každém okamžiku mají všechny uzavřené vrcholy ohodnocení
+menší nebo rovné ohodnocením všech otevřených vrcholů. Na~počátku to jistě platí.
+Nechť nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevřenými. Během jeho
+relaxace nemůžeme žádnou hodnotu snížit pod~$h(v)$, jelikož v~grafu s~nezápornými
+hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevřených vrcholů
+tedy neklesne pod hodnotu tohoto nově uzavřeného. Hodnoty dříve uzavřených vrcholů
+se nemohou nijak změnit.
 \qed
 
-Přímočará implementace Dijkstrova algoritmu by tedy pokaždé v~čase $\O(n)$
-vybrala otevřený vrchol s~nejmenším ohodnocením, v~čase $\O(n)$ ho relaxovala
-a toto by se opakovalo nejvýše $n$-krát. Algoritmus by tudíž doběhl v~čase $\O(n^2)$,
-což je pro husté grafy zajisté optimální. Zkusíme nyní zrychlit výpočet
-na~řídkých grafech.
-
-Vťechny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, takŞe úzkým hrdlem je
-vybírání minima. Použijeme pro něj vhodnou datovou strukturu, v~níž budeme udržovat
-množinu všech otevřených vrcholů spolu s~jejich ohodnoceními. Od~datové struktury
-potřebujeme, aby uměla operace \<Insert> (vložení vrcholu), \<ExtractMin> (nalezení
-a smazání minima) a \<Decrease> (snížení hodnoty vrcholu). První dvě operace přitom
-volåme nejvýťe $n$-kråt a operaci \<Decrease> nejvýťe $m$-kråt. Celý algoritmus
-tedy doběhne v~čase
+Přímočará implementace Dijkstrova algoritmu by tedy pokaždé v~čase $\O(n)$
+vybrala otevřený vrchol s~nejmenším ohodnocením, v~čase $\O(n)$ ho relaxovala
+a toto by se opakovalo nejvýše $n$-krát. Algoritmus by tudíž doběhl v~čase $\O(n^2)$,
+což je pro husté grafy zajisté optimální. Zkusíme nyní zrychlit výpočet
+na~řídkých grafech.
+
+Všechny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, takže úzkým hrdlem je
+vybírání minima. Použijeme pro něj vhodnou datovou strukturu, v~níž budeme udržovat
+množinu všech otevřených vrcholů spolu s~jejich ohodnoceními. Od~datové struktury
+potřebujeme, aby uměla operace \<Insert> (vložení vrcholu), \<ExtractMin> (nalezení
+a smazání minima) a \<Decrease> (snížení hodnoty vrcholu). První dvě operace přitom
+voláme nejvýše $n$-krát a operaci \<Decrease> nejvýše $m$-krát. Celý algoritmus
+tedy doběhne v~čase
 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
-kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou časové složitosti jednotlivých operací
-na~struktuře o~nejvýše~$n$ prvcích (stačí amortizovaně).
+kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou časové složitosti jednotlivých operací
+na~struktuře o~nejvýše~$n$ prvcích (stačí amortizovaně).
 
-\>JakĂŠ moĹžnosti mĂĄme pro volbu struktury?
+\>Jaké možnosti máme pro volbu struktury?
 
 \itemize\ibull
-\:{\I pole} -- \<Insert> a \<Decrease> stojĂ­ konstantu, \<ExtractMin> trvĂĄ $\O(n)$,
+\:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
   celkem tedy $\O(n^2)$.
-\:{\I (binární) halda} -- všechny tři operace umíme provést v~čase $\O(\log n)$, takže celkem
-  $\O(m\log n)$. To je pro husté grafy horší, pro řídké lepší.
-\:{\I $k$-regulĂĄrnĂ­ halda} -- pokud haldu upravĂ­me tak, Ĺže kaĹždĂ˝ prvek bude mĂ­t aĹž $k$ synĹŻ,
-  hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky směrem nahoru,
-  což je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ovšem \<ExtractMin> potřebuje
-  zkoumat vĹĄechny syny kaĹždĂŠho navĹĄtĂ­venĂŠho prvku, takĹže se zpomalĂ­ na $\O(k\log_k n)$.
-
-  Celková složitost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba členy se vyrovnají
-  pro $k=m/n$, čímž získáme $\O(m\log_{m/n} n)$. Člen $\log_{m/n} n$ je přitom $\O(1)$,
-  kdykoliv je $m\ge n^{1+\varepsilon}$ pro nějaké~$\varepsilon>0$, takže pro dostatečně
-  hustĂŠ grafy jsme zĂ­skali lineĂĄrnĂ­ algoritmus.
-
-  (Všimněte si, že pro $m\approx n^2$ algoritmus zvolí $k\approx n$, takže halda degeneruje
-  na jedinÊ patro, tedy na pole, kterÊ se opravdu ukåzalo být optimålní volbou pro hustÊ grafy.)
-\:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojĂ­ $\O(1)$, \<ExtractMin> mĂĄ sloĹžitost
-  $\O(\log n)$ [vše amortizovaně]. Dijkstrův algoritmus proto doběhne v~čase $\O(m + n\log n)$.
-  To je lineĂĄrnĂ­ pro grafy s~hustotou $\Omega(\log n)$. TĂŠĹže sloĹžitosti operacĂ­ dosahujĂ­
-  i jiné, méně známé haldy \cite{haeupler:rankph,elmasry:violheap}, které mohou být v~praxi
-  výrazně rychlejší.
-\:{\I Monotónní haldy} -- můžeme použít nějakou jinou haldu, která využívá toho,
-  že posloupnost odebíraných prvků je neklesající. Pro celá čísla na~\hbox{RAMu} to může
-  být například Thorupova halda \cite{thorup:queue} se složitostí $\O(\log\log n)$ u~operace \<ExtractMin>
-  a $\O(1)$ u~ostatních operací. Dijkstra tedy běží v~$\O(m + n\log\log n)$.
-\:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápětí.
+\:{\I (binární) halda} -- všechny tři operace umíme provést v~čase $\O(\log n)$, takže celkem
+  $\O(m\log n)$. To je pro husté grafy horší, pro řídké lepší.
+\:{\I $k$-regulární halda} -- pokud haldu upravíme tak, že každý prvek bude mít až $k$ synů,
+  hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky směrem nahoru,
+  což je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ovšem \<ExtractMin> potřebuje
+  zkoumat všechny syny každého navštíveného prvku, takže se zpomalí na $\O(k\log_k n)$.
+
+  Celková složitost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba členy se vyrovnají
+  pro $k=m/n$, čímž získáme $\O(m\log_{m/n} n)$. Člen $\log_{m/n} n$ je přitom $\O(1)$,
+  kdykoliv je $m\ge n^{1+\varepsilon}$ pro nějaké~$\varepsilon>0$, takže pro dostatečně
+  husté grafy jsme získali lineární algoritmus.
+
+  (Všimněte si, že pro $m\approx n^2$ algoritmus zvolí $k\approx n$, takže halda degeneruje
+  na jediné patro, tedy na pole, které se opravdu ukázalo být optimální volbou pro husté grafy.)
+\:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má složitost
+  $\O(\log n)$ [vše amortizovaně]. Dijkstrův algoritmus proto doběhne v~čase $\O(m + n\log n)$.
+  To je lineární pro grafy s~hustotou $\Omega(\log n)$. Téže složitosti operací dosahují
+  i jiné, méně známé haldy \cite{haeupler:rankph,elmasry:violheap}, které mohou být v~praxi
+  výrazně rychlejší.
+\:{\I Monotónní haldy} -- můžeme použít nějakou jinou haldu, která využívá toho,
+  že posloupnost odebíraných prvků je neklesající. Pro celá čísla na~\hbox{RAMu} to může
+  být například Thorupova halda \cite{thorup:queue} se složitostí $\O(\log\log n)$ u~operace \<ExtractMin>
+  a $\O(1)$ u~ostatních operací. Dijkstra tedy běží v~$\O(m + n\log\log n)$.
+\:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápětí.
 \endlist
 
-\s{Cvičení:}
+\s{Cvičení:}
 
 \itemize\ibull
-\:Najděte příklad grafu se zápornými hranami (ale bez záporných cyklů),
-  na~kterĂŠm DijkstrĹŻv algoritmus selĹže.
-\:Rozmyslete si, že pokud nevyužijeme nějaké speciální vlastnosti čísel (celočíselnost,
-  omezený rozsah), je mez $\O(m+n\log n)$ nejlepťí moŞnå, protoŞe Dijkstrovým algoritmem
-  můžeme třídit $n$-tici čísel. Thorup dokonce dokázal \cite{thorup:equiv}, že z~každého třídícího algoritmu
-  se sloĹžitostĂ­ $\O(nT(n))$ mĹŻĹžeme odvodit haldu se sloĹžitostĂ­ mazĂĄnĂ­ $\O(T(n))$.
-\:Jsou-li délky hran celočíselné, můžeme se na Dijkstrův algoritmus dívat i takto:
-  Představme si, že každou hranu nahradíme cestou tvořenou příslušným počtem hran jednotkové délky
-  a na vzniklý neohodnocený graf spustíme prohledávání do~šířky. To samozřejmě vydá
-  správný výsledek, ale poměrně pomalu, protože bude většinu času trávit posouváním
-  vlny \uv{uvnitř} původních hran. Můžeme si tedy pro každou původní hranu nařídit
-  \uv{budík}, který nám řekne, za~kolik posunutí vlny dospějeme na~její konec.
-  DokaŞte, Şe tento algoritmus je ekvivalentní s~Dijkstrovým.
+\:Najděte příklad grafu se zápornými hranami (ale bez záporných cyklů),
+  na~kterém Dijkstrův algoritmus selže.
+\:Rozmyslete si, že pokud nevyužijeme nějaké speciální vlastnosti čísel (celočíselnost,
+  omezený rozsah), je mez $\O(m+n\log n)$ nejlepší možná, protože Dijkstrovým algoritmem
+  můžeme třídit $n$-tici čísel. Thorup dokonce dokázal \cite{thorup:equiv}, že z~každého třídícího algoritmu
+  se složitostí $\O(nT(n))$ můžeme odvodit haldu se složitostí mazání $\O(T(n))$.
+\:Jsou-li délky hran celočíselné, můžeme se na Dijkstrův algoritmus dívat i takto:
+  Představme si, že každou hranu nahradíme cestou tvořenou příslušným počtem hran jednotkové délky
+  a na vzniklý neohodnocený graf spustíme prohledávání do~šířky. To samozřejmě vydá
+  správný výsledek, ale poměrně pomalu, protože bude většinu času trávit posouváním
+  vlny \uv{uvnitř} původních hran. Můžeme si tedy pro každou původní hranu nařídit
+  \uv{budík}, který nám řekne, za~kolik posunutí vlny dospějeme na~její konec.
+  Dokažte, že tento algoritmus je ekvivalentní s~Dijkstrovým.
 \endlist
 
-\h{Celočíselné délky}
-
-Uvažujme nyní grafy, v~nichž jsou všechny délky hran nezáporná celá čísla omezená
-nějakou konstantou~$L$. Všechny vzdálenosti jsou tedy omezeny číslem~$nL$, takže
-nám stačí datová struktura schopná uchovávat takto omezená celá čísla.
-
-Použijeme jednoduchou přihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
-jeho $i$-tĂ˝ prvek bude obsahovat seznam vrcholĹŻ, jejichĹž ohodnocenĂ­ je rovno~$i$.
-Operace \<Insert> a \<Decrease> zvládneme v~konstantním čase, budeme-li si u~každého
-prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potřebuje najít první
-neprázdnou přihrádku, ale jelikož víme, že posloupnost odebíraných minim je monotónní,
-stačí hledat od místa, kde se hledání zastavilo minule. Všechna hledání přihrádek
-tedy zaberou dohromady $\O(nL)$ a celĂ˝ DijkstrĹŻv algoritmus bude trvat $\O(nL + m)$.
-
-Prostorovå sloŞitost $\O(nL+m)$ je nevalnå, ale můŞeme ji jednoduchým trikem
-snížit: Všimneme si, že všechna konečná ohodnocení vrcholů nemohou být větší
-než aktuální minimum zvětšené o~$L$. Jinými slovy všechny neprázdné přihrádky
-se nacházejí v~úseku pole dlouhém~$L+1$, takže stačí indexovat modulo~$L+1$.
-Pouze si musíme dávat pozor, abychom správně poznali, kdy se struktura
-vyprázdnila, což zjistíme například pomocí počítadla otevřených vrcholů. Čas si
-asymptoticky nezhorĹĄĂ­me, prostor klesne na~$\O(L+m)$.
-
-Podobný trik můžeme použít i pro libovolnou jinou datovou strukturu: rozsah čísel
-rozdělíme na~\uv{okna} velikosti~$L$ (v~$i$-tém okně jsou čísla $iL,iL+1,\ldots,(i+1)L-1$).
-V~libovolné chvíli mohou tedy být neprázdná nejvýše dvě okna. Stačí nám proto
-pořídit si dvě struktury pro ukládání čísel v~rozsahu $0,\ldots,L-1$ -- jedna
-z~nich bude reprezentovat aktuální okno (to, v~němž leželo minulé minimum),
-druhá okno bezprostředně následující. Minimum mažeme z~první struktury; pokud
-už je prázdná, obě struktury prohodíme. Operace \<Insert> podle hodnoty určí,
-do~které struktury se má vkládat. S~operací \<Decrease> je to složitější --
-hodnota z~vyšší struktury může přeskočit do té nižší, ale v~takovém případě
-ji ve~vyšší struktuře vymažeme (to je \<Decrease> na $-\infty$ následovaný
-\<ExtractMin>em) a do~té nižší vložíme. To se každému prvku může přihodit nejvýše
-jednou, takže stále platí, že se každý prvek účastní $\O(1)$ vložení a $\O(1)$
-extrakcĂ­ minima.
-
-Ukázali jsme tedy, že pro naše potřeby postačuje struktura schopná uchovávání
-čísel menších nebo rovných~$L$.
-
-Nabízí se použít van Emde-Boasův strom z~kapitoly o~výpočetních modelech.
-Ten dosahuje sloĹžitosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
-operaci \<Decrease> musíme překládat na \<Delete> a \<Insert>. Celková
-složitost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, přičemž čas~$L$
-spotřebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
-viz zmíněná kapitola).
-
-Vraťme se ale ještě k~využití přihrádek\dots
-
-\h{Víceúrovňové přihrádky}
-
-Podobně jako u~třídění čísel, i~zde se vyplácí stavět přihrádkové struktury
-víceúrovňově (původně popsáno Goldbergem a Silversteinem \cite{goldberg:mlb}).
-Jednotlivé hodnoty budeme zapisovat v~soustavě o~základu~$B$,
-který zvolíme jako nějakou mocninu dvojky, abychom mohli s~číslicemi tohoto
-zápisu snadno zacházet pomocí bitových operací. Každé číslo tedy zabere nejvýše
-$d=1+\lfloor\log_B L\rfloor$ číslic; pokud bude kratší, doplníme ho zleva nulami.
-
-Nejvyšší patro struktury bude tvořeno polem $B$~přihrádek, v~$i$-té z~nich
-budou uložena ta čísla, jejichž číslice nejvyššího řádu je rovna~$i$. Za~{\I aktivní}
-prohlásíme tu přihrádku, která obsahuje aktuální minimum. Přihrádky s~menšími
-indexy jsou prázdné a zůstanou takové až do~konce výpočtu, protože halda
-je monotónní. Pokud v~přihrádce obsahující minimum bude více prvků, budeme
-ji rozkládat podle druhého nejvyššího řádu na dalších~$B$ přihrádek atd.
-Celkem tak vznikne aĹž~$d$ ĂşrovnĂ­.
-
-\>Struktura bude obsahovat nĂĄsledujĂ­cĂ­ data:
+\h{Celočíselné délky}
+
+Uvažujme nyní grafy, v~nichž jsou všechny délky hran nezáporná celá čísla omezená
+nějakou konstantou~$L$. Všechny vzdálenosti jsou tedy omezeny číslem~$nL$, takže
+nám stačí datová struktura schopná uchovávat takto omezená celá čísla.
+
+Použijeme jednoduchou přihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
+jeho $i$-tý prvek bude obsahovat seznam vrcholů, jejichž ohodnocení je rovno~$i$.
+Operace \<Insert> a \<Decrease> zvládneme v~konstantním čase, budeme-li si u~každého
+prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potřebuje najít první
+neprázdnou přihrádku, ale jelikož víme, že posloupnost odebíraných minim je monotónní,
+stačí hledat od místa, kde se hledání zastavilo minule. Všechna hledání přihrádek
+tedy zaberou dohromady $\O(nL)$ a celý Dijkstrův algoritmus bude trvat $\O(nL + m)$.
+
+Prostorová složitost $\O(nL+m)$ je nevalná, ale můžeme ji jednoduchým trikem
+snížit: Všimneme si, že všechna konečná ohodnocení vrcholů nemohou být větší
+než aktuální minimum zvětšené o~$L$. Jinými slovy všechny neprázdné přihrádky
+se nacházejí v~úseku pole dlouhém~$L+1$, takže stačí indexovat modulo~$L+1$.
+Pouze si musíme dávat pozor, abychom správně poznali, kdy se struktura
+vyprázdnila, což zjistíme například pomocí počítadla otevřených vrcholů. Čas si
+asymptoticky nezhoršíme, prostor klesne na~$\O(L+m)$.
+
+Podobný trik můžeme použít i pro libovolnou jinou datovou strukturu: rozsah čísel
+rozdělíme na~\uv{okna} velikosti~$L$ (v~$i$-tém okně jsou čísla $iL,iL+1,\ldots,(i+1)L-1$).
+V~libovolné chvíli mohou tedy být neprázdná nejvýše dvě okna. Stačí nám proto
+pořídit si dvě struktury pro ukládání čísel v~rozsahu $0,\ldots,L-1$ -- jedna
+z~nich bude reprezentovat aktuální okno (to, v~němž leželo minulé minimum),
+druhá okno bezprostředně následující. Minimum mažeme z~první struktury; pokud
+už je prázdná, obě struktury prohodíme. Operace \<Insert> podle hodnoty určí,
+do~které struktury se má vkládat. S~operací \<Decrease> je to složitější --
+hodnota z~vyšší struktury může přeskočit do té nižší, ale v~takovém případě
+ji ve~vyšší struktuře vymažeme (to je \<Decrease> na $-\infty$ následovaný
+\<ExtractMin>em) a do~té nižší vložíme. To se každému prvku může přihodit nejvýše
+jednou, takže stále platí, že se každý prvek účastní $\O(1)$ vložení a $\O(1)$
+extrakcí minima.
+
+Ukázali jsme tedy, že pro naše potřeby postačuje struktura schopná uchovávání
+čísel menších nebo rovných~$L$.
+
+Nabízí se použít van Emde-Boasův strom z~kapitoly o~výpočetních modelech.
+Ten dosahuje složitosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
+operaci \<Decrease> musíme překládat na \<Delete> a \<Insert>. Celková
+složitost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, přičemž čas~$L$
+spotřebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
+viz zmíněná kapitola).
+
+Vraťme se ale ještě k~využití přihrádek\dots
+
+\h{Víceúrovňové přihrádky}
+
+Podobně jako u~třídění čísel, i~zde se vyplácí stavět přihrádkové struktury
+víceúrovňově (původně popsáno Goldbergem a Silversteinem \cite{goldberg:mlb}).
+Jednotlivé hodnoty budeme zapisovat v~soustavě o~základu~$B$,
+který zvolíme jako nějakou mocninu dvojky, abychom mohli s~číslicemi tohoto
+zápisu snadno zacházet pomocí bitových operací. Každé číslo tedy zabere nejvýše
+$d=1+\lfloor\log_B L\rfloor$ číslic; pokud bude kratší, doplníme ho zleva nulami.
+
+Nejvyšší patro struktury bude tvořeno polem $B$~přihrádek, v~$i$-té z~nich
+budou uložena ta čísla, jejichž číslice nejvyššího řádu je rovna~$i$. Za~{\I aktivní}
+prohlásíme tu přihrádku, která obsahuje aktuální minimum. Přihrádky s~menšími
+indexy jsou prázdné a zůstanou takové až do~konce výpočtu, protože halda
+je monotónní. Pokud v~přihrádce obsahující minimum bude více prvků, budeme
+ji rozkládat podle druhého nejvyššího řádu na dalších~$B$ přihrádek atd.
+Celkem tak vznikne až~$d$ úrovní.
+
+\>Struktura bude obsahovat následující data:
 
 \itemize\ibull
 \:Parametry $L$, $B$ a~$d$.
-\:Pole úrovní (nejvyšší má číslo~$d-1$, nejnižší~0), každá úroveň je buďto prázdná
-  (a pak jsou prázdné i~všechny nižší), nebo obsahuje pole~$U_i$ o~$B$ přihrádkách
-  a v~kaŞdÊ z~nich seznam prvků. Pole úrovní pouŞívåme jako zåsobník, udrŞujeme
-  si číslo nejnižší neprázdné úrovně.
-\:Hodnotu~$\mu$ předchozího odebraného minima.
+\:Pole úrovní (nejvyšší má číslo~$d-1$, nejnižší~0), každá úroveň je buďto prázdná
+  (a pak jsou prázdné i~všechny nižší), nebo obsahuje pole~$U_i$ o~$B$ přihrádkách
+  a v~každé z~nich seznam prvků. Pole úrovní používáme jako zásobník, udržujeme
+  si číslo nejnižší neprázdné úrovně.
+\:Hodnotu~$\mu$ předchozího odebraného minima.
 \endlist
 
-Operace \<Insert> vloží hodnotu do~nejhlubší možné přihrádky. Podívá se tedy
-na~nejvyšší úroveň: pokud hodnota patří do přihrádky, která není aktivní, vloží
-ji přímo. Jinak přejde o~úroveň níže a zopakuje stejný postup. To vše lze provést
-v~konstantním čase: stačí se podívat, jaký je nejvyšší jedničkový bit ve~{\sc xor}u
-nové hodnoty s~číslem~$\mu$ (opět viz kapitola o~výpočetních modelech), a tím zjistit
-číslo úrovně, kam hodnota patří.
+Operace \<Insert> vloží hodnotu do~nejhlubší možné přihrádky. Podívá se tedy
+na~nejvyšší úroveň: pokud hodnota patří do přihrádky, která není aktivní, vloží
+ji přímo. Jinak přejde o~úroveň níže a zopakuje stejný postup. To vše lze provést
+v~konstantním čase: stačí se podívat, jaký je nejvyšší jedničkový bit ve~{\sc xor}u
+nové hodnoty s~číslem~$\mu$ (opět viz kapitola o~výpočetních modelech), a tím zjistit
+číslo úrovně, kam hodnota patří.
 
-Pokud chceme provést \<Decrease>, odstraníme hodnotu z~přihrádky, ve~které se
-právě nachází (polohu si můžeme u~každé hodnoty pamatovat zvlášť), a znovu ji
-vloŞíme.
+Pokud chceme provést \<Decrease>, odstraníme hodnotu z~přihrádky, ve~které se
+právě nachází (polohu si můžeme u~každé hodnoty pamatovat zvlášť), a znovu ji
+vložíme.
 
-Většinu práce samozřejmě přenecháme funkci \<ExtractMin>. Ta začne prohledávat
-nejnižší obsazenou úroveň od~aktivní přihrádky dál (to, která přihrádka je na
-které úrovni aktivní, poznáme z~číslic hodnoty~$\mu$). Pokud přihrádky na~této
-úrovni dojdou, prázdnou úroveň zrušíme a pokračujeme o~patro výše.
+Většinu práce samozřejmě přenecháme funkci \<ExtractMin>. Ta začne prohledávat
+nejnižší obsazenou úroveň od~aktivní přihrádky dál (to, která přihrádka je na
+které úrovni aktivní, poznáme z~číslic hodnoty~$\mu$). Pokud přihrádky na~této
+úrovni dojdou, prázdnou úroveň zrušíme a pokračujeme o~patro výše.
 
-Jakmile najdeme neprázdnou přihrádku, nalezneme v~ní minimum a to se stane novým~$\mu$.
-Pokud v~přihrádce nebyly žádné další prvky, skončíme. V~opačném případě zbývající
-prvky rozprostřeme do~přihrádek na~bezprostředně nižší úrovni, kterou tím založíme.
+Jakmile najdeme neprázdnou přihrádku, nalezneme v~ní minimum a to se stane novým~$\mu$.
+Pokud v~přihrádce nebyly žádné další prvky, skončíme. V~opačném případě zbývající
+prvky rozprostřeme do~přihrádek na~bezprostředně nižší úrovni, kterou tím založíme.
 
-Čas strávený hledáním minima můžeme rozdělit na~několik částí:
+Čas strávený hledáním minima můžeme rozdělit na~několik částí:
 
 \itemize\ibull
-\:$\O(B)$ na inicializaci nové úrovně -- to naúčtujeme prvku, který jsme
-  právě mazali;
-\:hledání neprázdných přihrádek -- prozkoumání každé prázdné přihrádky
-  naúčtujeme jejímu vytvoření, což se rozpustí v~$\O(B)$ na inicializaci
-  úrovně;
-\:zrušení úrovně -- opět naúčtujeme jejímu vzniku;
-\:rozhazování prvků do přihrádek -- jelikož prvky v~hierarchii přihrádek
-  putují během operací pouze doleva a dolů (jejich hodnoty se nikdy nezvětšují),
-  klesne každý prvek nejvýše~$d$-krát, takže stačí, když na všechna rozhazování
-  přispěje časem $\O(d)$.
+\:$\O(B)$ na inicializaci nové úrovně -- to naúčtujeme prvku, který jsme
+  právě mazali;
+\:hledání neprázdných přihrádek -- prozkoumání každé prázdné přihrádky
+  naúčtujeme jejímu vytvoření, což se rozpustí v~$\O(B)$ na inicializaci
+  úrovně;
+\:zrušení úrovně -- opět naúčtujeme jejímu vzniku;
+\:rozhazování prvků do přihrádek -- jelikož prvky v~hierarchii přihrádek
+  putují během operací pouze doleva a dolů (jejich hodnoty se nikdy nezvětšují),
+  klesne každý prvek nejvýše~$d$-krát, takže stačí, když na všechna rozhazování
+  přispěje časem $\O(d)$.
 \endlist
 
-\>Stačí tedy, aby každý prvek při \<Insert>u zaplatil čas $\O(B+d)$ a jak \<Decrease>,
-tak \<ExtractMin> budou mĂ­t konstantnĂ­ amortizovanou sloĹžitost. DijkstrĹŻv
-algoritmus pak poběží v~$\O(m + n(B+d))$.
+\>Stačí tedy, aby každý prvek při \<Insert>u zaplatil čas $\O(B+d)$ a jak \<Decrease>,
+tak \<ExtractMin> budou mít konstantní amortizovanou složitost. Dijkstrův
+algoritmus pak poběží v~$\O(m + n(B+d))$.
 
-Zbývå nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
-Vhodná volba je $B=\log L/\log\log L$. Při ní platí
+Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
+Vhodná volba je $B=\log L/\log\log L$. Při ní platí
 $$
 {\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
 = {\log L\over \log\log L - \log\log\log L} = \Theta(B).
 $$
-Tehdy Dijkstra vydá výsledek v~čase $\O(m + n\cdot{\log L\over\log\log L})$.
-
-\h{HOT Queue -- kombinace přihrádek s~haldou}
-
-Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si všimli, že ve~víceúrovňových přihrádkových strukturách
-platíme příliš mnoho za~úrovně, ve~kterých se za~dobu jejich existence objeví jen malé
-množství prvků. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~společné haldy.
-Výsledné struktuře se říká HOT (Heap-on-Top) Queue. My si předvedeme její upravenou
-variantu (v~té původní se skrývá několik chyb).
-
-Pořídíme si haldu, řekněme Fibonacciho, a~navíc ke~každé úrovni počítadlo udávající,
-kolik prvků z~této úrovně jsme uložili do~haldy. Dokud toto počítadlo nepřeroste nějaký
-parametr~$H$, přihrádky nebudeme zakládat a prvky poputují do~haldy. Čas $\O(B)$ na
-založení úrovně a její procházení proto můžeme rozpočítat mezi~$H$ prvků, které se musely
-na~dané úrovni objevit, než byla rozpřihrádkována. (Povšimněte si, že počítadlo nikdy
-nesniŞujeme, pouze ho vynulujeme, kdyŞ je úroveň zruťena. Proto vůbec nemusí odpovídat
-skutečnému počtu prvků z~příslušné úrovně, které jsou právě uloženy v~haldě. To ovšem
-vůbec nevadí -- počítadlo pouze hlídá, aby se úroveň nevytvořila příliš brzy, tedy abychom
-měli dost prvků k~rozúčtování času.)
-
-Proměnnou~$\mu$ necháme ukazovat na~místo, kde jsme se při hledání minima v~přihrádkách
-zastavili. Současné globální minimum struktury může být nižší, nachází-li se minimum
-zrovna v~haldě. Stále je však zaručeno, že před~$\mu$ se nenachází žádná
-neprázdná přihrádka.
+Tehdy Dijkstra vydá výsledek v~čase $\O(m + n\cdot{\log L\over\log\log L})$.
+
+\h{HOT Queue -- kombinace přihrádek s~haldou}
+
+Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si všimli, že ve~víceúrovňových přihrádkových strukturách
+platíme příliš mnoho za~úrovně, ve~kterých se za~dobu jejich existence objeví jen malé
+množství prvků. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~společné haldy.
+Výsledné struktuře se říká HOT (Heap-on-Top) Queue. My si předvedeme její upravenou
+variantu (v~té původní se skrývá několik chyb).
+
+Pořídíme si haldu, řekněme Fibonacciho, a~navíc ke~každé úrovni počítadlo udávající,
+kolik prvků z~této úrovně jsme uložili do~haldy. Dokud toto počítadlo nepřeroste nějaký
+parametr~$H$, přihrádky nebudeme zakládat a prvky poputují do~haldy. Čas $\O(B)$ na
+založení úrovně a její procházení proto můžeme rozpočítat mezi~$H$ prvků, které se musely
+na~dané úrovni objevit, než byla rozpřihrádkována. (Povšimněte si, že počítadlo nikdy
+nesnižujeme, pouze ho vynulujeme, když je úroveň zrušena. Proto vůbec nemusí odpovídat
+skutečnému počtu prvků z~příslušné úrovně, které jsou právě uloženy v~haldě. To ovšem
+vůbec nevadí -- počítadlo pouze hlídá, aby se úroveň nevytvořila příliš brzy, tedy abychom
+měli dost prvků k~rozúčtování času.)
+
+Proměnnou~$\mu$ necháme ukazovat na~místo, kde jsme se při hledání minima v~přihrádkách
+zastavili. Současné globální minimum struktury může být nižší, nachází-li se minimum
+zrovna v~haldě. Stále je však zaručeno, že před~$\mu$ se nenachází žádná
+neprázdná přihrádka.
 
 Operace budou fungovat takto:
 
 \>\<Insert>:
 \algo
-\:Spočítáme, do~které úrovně~$i$ má prvek padnout (bitovými operacemi).
-\:Pokud je počítadlo této úrovně menší než~$H$, zvýšíme ho, vložíme prvek do~haldy a skočíme.
-\:Nebyly-li ještě pro tuto úroveň založeny přihrádky, vyrobíme prázdné.
-\:Vložíme prvek do~příslušné přihrádky.
+\:Spočítáme, do~které úrovně~$i$ má prvek padnout (bitovými operacemi).
+\:Pokud je počítadlo této úrovně menší než~$H$, zvýšíme ho, vložíme prvek do~haldy a skočíme.
+\:Nebyly-li ještě pro tuto úroveň založeny přihrádky, vyrobíme prázdné.
+\:Vložíme prvek do~příslušné přihrádky.
 \endalgo
 
 \>\<Decrease>:
 \algo
-\:Pokud se prvek nachází v~haldě (to si u~každého prvku pamatujeme), provedeme
-  \<Decrease> v~haldě a skončíme.
-\:Smažeme prvek z~jeho přihrádky a provedeme \<Insert> s~novou hodnotou.
+\:Pokud se prvek nachází v~haldě (to si u~každého prvku pamatujeme), provedeme
+  \<Decrease> v~haldě a skončíme.
+\:Smažeme prvek z~jeho přihrádky a provedeme \<Insert> s~novou hodnotou.
 \endalgo
 
 \>\<ExtractMin>:
 \algo
-\:Dokud je~$\mu$ menĹĄĂ­ neĹž aktuĂĄlnĂ­ minimum haldy, opakujeme:
-\::Najdeme přihrádku odpovídající hodnotě~$\mu$.
-\::Je-li tato přihrádka prázdná, přejdeme na~další (upravíme~$\mu$). Jsme-li na konci úrovně,
-   zrušíme ji, vynulujeme její počítadlo a pokračujeme o~úroveň výš.
-\::Není-li prázdná, rozprostřeme ji o~úroveň níž (stejným způsobem jako při \<Insert>u,
-   takŞe prvních~$H$ prvků vloŞíme do~haldy).
-\:SmaŞeme minimum z~haldy a vråtíme ho jako výsledek.
+\:Dokud je~$\mu$ menší než aktuální minimum haldy, opakujeme:
+\::Najdeme přihrádku odpovídající hodnotě~$\mu$.
+\::Je-li tato přihrádka prázdná, přejdeme na~další (upravíme~$\mu$). Jsme-li na konci úrovně,
+   zrušíme ji, vynulujeme její počítadlo a pokračujeme o~úroveň výš.
+\::Není-li prázdná, rozprostřeme ji o~úroveň níž (stejným způsobem jako při \<Insert>u,
+   takže prvních~$H$ prvků vložíme do~haldy).
+\:Smažeme minimum z~haldy a vrátíme ho jako výsledek.
 \endalgo
 
-\>Pustíme se do~analýzy složitosti. Jako parametry si zvolíme počet hladin~$d$ (takže
-počet přihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
+\>Pustíme se do~analýzy složitosti. Jako parametry si zvolíme počet hladin~$d$ (takže
+počet přihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
 
-Nejprve si všimneme, že než počítadlo nějaké úrovně vynulujeme, jsou bezpečně
-z~haldy pryč všechny prvky patřící do~této úrovně. Celkem se tedy v~haldě
-vyskytuje nejvýše $\O(dH)$ prvků. \<ExtractMin> v~haldě proto trvá $\O(\log(dH))$,
-ostatnĂ­ haldovĂŠ operace $\O(1)$.
+Nejprve si všimneme, že než počítadlo nějaké úrovně vynulujeme, jsou bezpečně
+z~haldy pryč všechny prvky patřící do~této úrovně. Celkem se tedy v~haldě
+vyskytuje nejvýše $\O(dH)$ prvků. \<ExtractMin> v~haldě proto trvá $\O(\log(dH))$,
+ostatní haldové operace $\O(1)$.
 
-Nyní rozúčtujeme čas operací mezi jednotlivé prvky (opět si vše předplatíme
-v~\<Insert>u a ostatní operace poběží v~amortizovaně konstantním čase):
+Nyní rozúčtujeme čas operací mezi jednotlivé prvky (opět si vše předplatíme
+v~\<Insert>u a ostatní operace poběží v~amortizovaně konstantním čase):
 
 \itemize\ibull
-\:KaŞdý prvek můŞe být nejvýťe jednou za~dobu svÊho Şivota vloŞen do~haldy
-  a nejvýše jednou z~ní vyjmut. Na~obojí dohromady přispěje $\O(\log dH)$.
-\:Prvek se účastní nejvýše~$d$ přehození do~nižší úrovně. Pokud byl přihozen
-  do~haldy, už tam setrvá, jinak pokaždé zaplatí $\O(1)$ za~zařazení do~přihrádky,
+\:Každý prvek může být nejvýše jednou za~dobu svého života vložen do~haldy
+  a nejvýše jednou z~ní vyjmut. Na~obojí dohromady přispěje $\O(\log dH)$.
+\:Prvek se účastní nejvýše~$d$ přehození do~nižší úrovně. Pokud byl přihozen
+  do~haldy, už tam setrvá, jinak pokaždé zaplatí $\O(1)$ za~zařazení do~přihrádky,
   celkem tedy $\O(d)$ na prvek.
-\:Vytvoření, projití a smazání přihrádek na~jedné úrovni nastane až tehdy, co bylo
-  $H$~prvků patřících do~této úrovně vloženo do~haldy. Stačí tedy, aby každý
-  prvek přispěl časem $\O(B/H) = \O(L^{1/d}/H)$.
+\:Vytvoření, projití a smazání přihrádek na~jedné úrovni nastane až tehdy, co bylo
+  $H$~prvků patřících do~této úrovně vloženo do~haldy. Stačí tedy, aby každý
+  prvek přispěl časem $\O(B/H) = \O(L^{1/d}/H)$.
 \endlist
 
-\>KaĹždĂ˝ prvek tedy platĂ­ $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
-Pojďme najít nastavení parametrů, které tento výraz minimalizuje.
+\>Každý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
+Pojďme najít nastavení parametrů, které tento výraz minimalizuje.
 Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
-Celý výraz tím zjednoduťíme na $\O(d + \log\,(L^{1/d}/d))$ =
-$\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sčítance volbou
-$d=\sqrt{\log L}$ vyrovnĂĄme.
+Celý výraz tím zjednodušíme na $\O(d + \log\,(L^{1/d}/d))$ =
+$\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sčítance volbou
+$d=\sqrt{\log L}$ vyrovnáme.
 
-HOT Queue tedy zvládne \<Insert> s~amortizovanou časovou složitostí $\O(\sqrt{\log L})$
-a ostatní operace v~čase amortizovaně konstantním. Použijeme-li tuto strukturu
-v~Dijkstrově algoritmu, spočte vzdálenosti v~čase $\O(m + n\sqrt{\log L})$.
+HOT Queue tedy zvládne \<Insert> s~amortizovanou časovou složitostí $\O(\sqrt{\log L})$
+a ostatní operace v~čase amortizovaně konstantním. Použijeme-li tuto strukturu
+v~Dijkstrově algoritmu, spočte vzdálenosti v~čase $\O(m + n\sqrt{\log L})$.
 
-\h{DinicĹŻv algoritmus}
+\h{Dinicův algoritmus}
 
-ZajĂ­mavĂŠ vylepĹĄenĂ­ Dijkstrova algoritmu navrhl Dinic. VĹĄiml si, Ĺže pokud
-je kaŞdå hrana dlouhå alespoň~$\delta$, můŞeme uzavírat nejen
-vrchol s~minimĂĄlnĂ­m ohodnocenĂ­m~$\mu$, ale i vĹĄechny s~ohodnocenĂ­m
-menĹĄĂ­m neĹž $\mu+\delta$.
+Zajímavé vylepšení Dijkstrova algoritmu navrhl Dinic. Všiml si, že pokud
+je každá hrana dlouhá alespoň~$\delta$, můžeme uzavírat nejen
+vrchol s~minimálním ohodnocením~$\mu$, ale i všechny s~ohodnocením
+menším než $\mu+\delta$.
 
-Pro takto upravený Dijkstrův algoritmus bude stále platit, že při uzavírání
-vrcholu odpovídá ohodnocení skutečné vzdálenosti, takže uzavřené vrcholy již
-nejsou znovu otevĂ­rĂĄny.
+Pro takto upravený Dijkstrův algoritmus bude stále platit, že při uzavírání
+vrcholu odpovídá ohodnocení skutečné vzdálenosti, takže uzavřené vrcholy již
+nejsou znovu otevírány.
 
-O~monotonii vzdáleností jsme sice přišli, ale v~přihrádkové struktuře nebo
-haldě můžeme klíče nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
-Tyto hodnoty se totiž chovají monotónně a vrcholy se stejným $h'(v)$ můžeme
-libovolně zaměňovat.
+O~monotonii vzdáleností jsme sice přišli, ale v~přihrádkové struktuře nebo
+haldě můžeme klíče nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
+Tyto hodnoty se totiž chovají monotónně a vrcholy se stejným $h'(v)$ můžeme
+libovolně zaměňovat.
 
-Kteroukoli z~popsaných přihrádkových struktur můžeme tedy použít, pouze
-v~rozboru časové složitosti nahradíme~$L$ výrazem $L/\delta$. Tento přístup
-přitom funguje i pro neceločíselné délky hran, pouze potřebujeme mít předem
-k~dispozici netriviĂĄlnĂ­ dolnĂ­ odhad na~vĹĄechny dĂŠlky.
+Kteroukoli z~popsaných přihrádkových struktur můžeme tedy použít, pouze
+v~rozboru časové složitosti nahradíme~$L$ výrazem $L/\delta$. Tento přístup
+přitom funguje i pro neceločíselné délky hran, pouze potřebujeme mít předem
+k~dispozici netriviální dolní odhad na~všechny délky.
 
-\h{PotenciĂĄly}
+\h{Potenciály}
 
-Viděli jsme, že v~grafech s~nezápornými délkami hran se nejkratší cesty
-hledají snáze. Nabízí se nalézt nějakou transformaci, která by
-dovedla délky hran upravit tak, aby byly nejkratší cesty zachovány (samozřejmě
-ne jejich dÊlky, ale alespoň to, kterÊ cesty jsou nejkratťí). Nabízí se
-nĂĄsledujĂ­cĂ­ fyzikĂĄlnĂ­ inspirace:
+Viděli jsme, že v~grafech s~nezápornými délkami hran se nejkratší cesty
+hledají snáze. Nabízí se nalézt nějakou transformaci, která by
+dovedla délky hran upravit tak, aby byly nejkratší cesty zachovány (samozřejmě
+ne jejich délky, ale alespoň to, které cesty jsou nejkratší). Nabízí se
+následující fyzikální inspirace:
 
-\s{Definice:} {\I Potenciál} budeme říkat libovolné funkci $\psi: V\rightarrow {\bb R}$.
-Pro kaĹždĂ˝ potenciĂĄl zavedeme {\I redukovanĂŠ dĂŠlky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
-Potenciál nazveme {\I přípustný,} pokud žádná hrana nemá zápornou redukovanou délku.
+\s{Definice:} {\I Potenciál} budeme říkat libovolné funkci $\psi: V\rightarrow {\bb R}$.
+Pro každý potenciál zavedeme {\I redukované délky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
+Potenciál nazveme {\I přípustný,} pokud žádná hrana nemá zápornou redukovanou délku.
 
-\s{PozorovĂĄnĂ­:} Pro redukovanou dĂŠlku libovolnĂŠ cesty~$P$ z~$u$ do~$v$ platĂ­: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.
+\s{Pozorování:} Pro redukovanou délku libovolné cesty~$P$ z~$u$ do~$v$ platí: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.
 
 \proof
-Nechť cesta~$P$ prochází přes vrcholy $u=w_1,\ldots,w_k=v$. Potom:
+Nechť cesta~$P$ prochází přes vrcholy $u=w_1,\ldots,w_k=v$. Potom:
 $$
 \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).
 $$
-Tato suma je ovĹĄem teleskopickĂĄ, takĹže z~nĂ­ zbude
+Tato suma je ovšem teleskopická, takže z~ní zbude
 $$
 \sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k) = \ell(P) + \psi(u) - \psi(v).
 $$
 \vskip-\baselineskip
 \qed
 
-\s{DĹŻsledek:} PotenciĂĄlovou redukcĂ­ se dĂŠlky vĹĄech cest mezi~$u$ a~$v$
-změní o~tutéž konstantu, takže struktura nejkratších cest zůstane nezměněna.
+\s{Důsledek:} Potenciálovou redukcí se délky všech cest mezi~$u$ a~$v$
+změní o~tutéž konstantu, takže struktura nejkratších cest zůstane nezměněna.
 
-Zbývá přijít na~to, kde si obstarat nějaký přípustný potenciál. Přidejme do~grafu
-nový vrchol~$z$, přiveďme z~něj hrany nulové délky do~všech ostatních vrcholů
-a~označme~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál
-přípustný, musí pro každou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
-Tuto nerovnost můžeme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, čili
-$d(z,u) + \ell(u,v) \ge d(z,v)$, což je ale obyčejná trojúhelníková nerovnost
-pro vzdálenost v~grafu, která jistě platí.
+Zbývá přijít na~to, kde si obstarat nějaký přípustný potenciál. Přidejme do~grafu
+nový vrchol~$z$, přiveďme z~něj hrany nulové délky do~všech ostatních vrcholů
+a~označme~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál
+přípustný, musí pro každou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
+Tuto nerovnost můžeme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, čili
+$d(z,u) + \ell(u,v) \ge d(z,v)$, což je ale obyčejná trojúhelníková nerovnost
+pro vzdálenost v~grafu, která jistě platí.
 
-Jedním výpočtem nejkratších cest v~grafu se zápornými hranami (třeba algoritmem BFM)
-tedy dokážeme spočítat potenciál, který nám poslouží k~redukci všech hran na~nezáporné
-délky. To nám samozřejmě nepomůže, chceme-li jednorázově hledat nejkratší cestu,
-ale může nám to výrazně zjednodušit další, složitější práci s~grafem. Jak uvidíme
-v~příští kapitole, můžeme tak například nalézt vzdálenosti mezi všemi dvojicemi
-vrcholů v~čase $\O(nm + n^2\log n)$.
+Jedním výpočtem nejkratších cest v~grafu se zápornými hranami (třeba algoritmem BFM)
+tedy dokážeme spočítat potenciál, který nám poslouží k~redukci všech hran na~nezáporné
+délky. To nám samozřejmě nepomůže, chceme-li jednorázově hledat nejkratší cestu,
+ale může nám to výrazně zjednodušit další, složitější práci s~grafem. Jak uvidíme
+v~příští kapitole, můžeme tak například nalézt vzdálenosti mezi všemi dvojicemi
+vrcholů v~čase $\O(nm + n^2\log n)$.
 
-Na~závěr tohoto oddílu dokážeme jedno pomocné tvrzení o~potenciálech, které
-nĂĄm pomĹŻĹže v~konstrukci algoritmĹŻ typu \ppsp:
+Na~závěr tohoto oddílu dokážeme jedno pomocné tvrzení o~potenciálech, které
+nám pomůže v~konstrukci algoritmů typu \ppsp:
 
-\s{Lemma:} Pokud $f$ a~$g$ jsou přípustné potenciály, pak jsou jimi i:
+\s{Lemma:} Pokud $f$ a~$g$ jsou přípustné potenciály, pak jsou jimi i:
 \numlist\ndotted
-\:konvexnĂ­ kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolnĂŠ $\alpha,\beta\ge 0, \alpha+\beta=1$;
+\:konvexní kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolné $\alpha,\beta\ge 0, \alpha+\beta=1$;
 \:$\min(f,g)$;
 \:$\max(f,g)$.
 \endlist
 
-\proof Buď $uv$ hrana. Potom z~definice přípustnosti platí $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$.
-Jednotlivé části tvrzení dokážeme takto:
+\proof Buď $uv$ hrana. Potom z~definice přípustnosti platí $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$.
+Jednotlivé části tvrzení dokážeme takto:
 \numlist\ndotted
-\:Pokud obě strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$
-  konstantou~$\beta$ a obě nerovnosti sečteme, dostaneme:
+\:Pokud obě strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$
+  konstantou~$\beta$ a obě nerovnosti sečteme, dostaneme:
   $$
   (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)),
   $$
-  což je přesně požadovaná nerovnost pro přípustnost funkce $\alpha f+\beta g$.
-\:Označme $h := \min(f,g)$. Nechť bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$,
-  shoduje se minimum s~funkcí~$f$ a není co dokazovat. V~opačném případě je $h(u) = f(u)$, $h(v) = g(v)$.
-  Tehdy si stačí všimnout, že $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, takže
-  potenciál~$h$ je přípustný.
-\:DokĂĄĹžeme analogicky.
+  což je přesně požadovaná nerovnost pro přípustnost funkce $\alpha f+\beta g$.
+\:Označme $h := \min(f,g)$. Nechť bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$,
+  shoduje se minimum s~funkcí~$f$ a není co dokazovat. V~opačném případě je $h(u) = f(u)$, $h(v) = g(v)$.
+  Tehdy si stačí všimnout, že $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, takže
+  potenciál~$h$ je přípustný.
+\:Dokážeme analogicky.
 \qeditem
 \endlist
 
-\h{Algoritmy pro problĂŠm typu \ppsp}
-
-Zaměřme se nyní na~případ, kdy chceme hledat nejkratší cesty mezi zadanou dvojicí
-vrcholů $s$,~$t$. Obvykle se i v~tÊto situaci pouŞívají algoritmy \sssp{} (SSSP) a v~obecnÊm
-případě ani není efektivnější řešení známo. Existuje ovšem velké množství heuristik, kterými
-lze obvykle výpočet zrychlit. Některé z~nich si předvedeme na Dijkstrově algoritmu.
-
-Dijkstrův algoritmus ve~své klasické podobě neví vůbec nic o~cílovém vrcholu a
-prohledá celý graf. Hned se nabízí využít toho, že od~okamžiku uzavření
-kteréhokoliv vrcholu se již jeho ohodnocení nezmění. Pokud tedy uzavřeme cílový
-vrchol, mĹŻĹžeme se zastavit.
-
-Jakou část grafu prohledáváme teď? V~metrice dané vzdálenostmi v~grafu je to nejmenší
-koule se středem ve~vrcholu~$u$, která obsahuje nejkratší cestu (dobře se to
-představuje na~hledání v~silniční síti na~rovinné mapě).
-
-TakÊ můŞeme spustit prohledåvåní z~obou konců zåroveň, tedy zkombinovat hledåní
-od~$s$ v~pĹŻvodnĂ­m grafu s~hledĂĄnĂ­m od~$t$ v~grafu s~obrĂĄcenou orientacĂ­ hran.
-Oba postupy můžeme libovolně střídat a zastavíme se v~okamžiku, kdy jsme jeden
-vrchol uzavřeli v~obou směrech. Pozor ovšem na to, že součet obou ohodnocení
-tohoto vrcholu nemusí být roven $d(v,u)$ -- zkuste vymyslet protipříklad.
-Nejkratší cesta ještě může vypadat tak, že přechází po nějaké hraně mezi vrcholem
-uzavřeným v~jednom směru a vrcholem uzavřeným ve~směru druhém (ponechme bez důkazu).
-Stačí tedy během relaxace zjistit, zda je konec hrany uzavřený v~opačném
-směru prohledávání, a~pokud ano, započítat cestu do~průběžného minima.
-
-Obousměrný Dijkstrův algoritmus projde sjednocení nějaké koule okolo~$s$ s~nějakou
-koulí okolo~$t$, které obsahuje nejkratší cestu. Průměry koulí přitom závisí na tom,
-jak budeme během výpočtu střídat oba směry prohledávání. V~nejhorším případě samozřejmě
-mĹŻĹžeme prohledat celĂ˝ graf.
+\h{Algoritmy pro problém typu \ppsp}
+
+Zaměřme se nyní na~případ, kdy chceme hledat nejkratší cesty mezi zadanou dvojicí
+vrcholů $s$,~$t$. Obvykle se i v~této situaci používají algoritmy \sssp{} (SSSP) a v~obecném
+případě ani není efektivnější řešení známo. Existuje ovšem velké množství heuristik, kterými
+lze obvykle výpočet zrychlit. Některé z~nich si předvedeme na Dijkstrově algoritmu.
+
+Dijkstrův algoritmus ve~své klasické podobě neví vůbec nic o~cílovém vrcholu a
+prohledá celý graf. Hned se nabízí využít toho, že od~okamžiku uzavření
+kteréhokoliv vrcholu se již jeho ohodnocení nezmění. Pokud tedy uzavřeme cílový
+vrchol, můžeme se zastavit.
+
+Jakou část grafu prohledáváme teď? V~metrice dané vzdálenostmi v~grafu je to nejmenší
+koule se středem ve~vrcholu~$u$, která obsahuje nejkratší cestu (dobře se to
+představuje na~hledání v~silniční síti na~rovinné mapě).
+
+Také můžeme spustit prohledávání z~obou konců zároveň, tedy zkombinovat hledání
+od~$s$ v~původním grafu s~hledáním od~$t$ v~grafu s~obrácenou orientací hran.
+Oba postupy můžeme libovolně střídat a zastavíme se v~okamžiku, kdy jsme jeden
+vrchol uzavřeli v~obou směrech. Pozor ovšem na to, že součet obou ohodnocení
+tohoto vrcholu nemusí být roven $d(v,u)$ -- zkuste vymyslet protipříklad.
+Nejkratší cesta ještě může vypadat tak, že přechází po nějaké hraně mezi vrcholem
+uzavřeným v~jednom směru a vrcholem uzavřeným ve~směru druhém (ponechme bez důkazu).
+Stačí tedy během relaxace zjistit, zda je konec hrany uzavřený v~opačném
+směru prohledávání, a~pokud ano, započítat cestu do~průběžného minima.
+
+Obousměrný Dijkstrův algoritmus projde sjednocení nějaké koule okolo~$s$ s~nějakou
+koulí okolo~$t$, které obsahuje nejkratší cestu. Průměry koulí přitom závisí na tom,
+jak budeme během výpočtu střídat oba směry prohledávání. V~nejhorším případě samozřejmě
+můžeme prohledat celý graf.
 
 \h{Algoritmus \astar}
 
-V~umělé inteligenci se často pro hledání nejkratší cesty v~rozsáhlých grafech
-(obvykle stavových prostorech úloh) pouŞívå algoritmus nazývaný~\astar{} \cite{hart:astar}.
-Jednå se o~modifikaci Dijkstrova algoritmu, kterå vyuŞívå heuristickou funkci
-pro dolní odhad vzdálenosti do~cíle; označme si ji $\psi(v)$. V~každém kroku pak uzavíra
-vrchol~$v$ s~nejmenším možným součtem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.
+V~umělé inteligenci se často pro hledání nejkratší cesty v~rozsáhlých grafech
+(obvykle stavových prostorech úloh) používá algoritmus nazývaný~\astar{} \cite{hart:astar}.
+Jedná se o~modifikaci Dijkstrova algoritmu, která využívá heuristickou funkci
+pro dolní odhad vzdálenosti do~cíle; označme si ji $\psi(v)$. V~každém kroku pak uzavíra
+vrchol~$v$ s~nejmenším možným součtem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.
 
-Intuice za tímto algoritmem je jasná: pokud víme, že nějaký vrchol je blízko
-od~počátačního vrcholu~$s$, ale bude z~něj určitě daleko do cíle~$t$, zatím ho
-odložíme a budeme zkoumat nadějnější varianty.
+Intuice za tímto algoritmem je jasná: pokud víme, že nějaký vrchol je blízko
+od~počátačního vrcholu~$s$, ale bude z~něj určitě daleko do cíle~$t$, zatím ho
+odložíme a budeme zkoumat nadějnější varianty.
 
-Heuristika se přitom volí podle konkrétního problému -- např. hledáme-li cestu
-v~mapě, můžeme použít vzdálenost do~cíle vzdušnou čarou.
+Heuristika se přitom volí podle konkrétního problému -- např. hledáme-li cestu
+v~mapě, můžeme použít vzdálenost do~cíle vzdušnou čarou.
 
-Je u~tohoto algoritmu zaručeno, že vždy najde nejkratší cestu? Na to nám dá odpověď
-teorie potenciĂĄlĹŻ:
+Je u~tohoto algoritmu zaručeno, že vždy najde nejkratší cestu? Na to nám dá odpověď
+teorie potenciálů:
 
-\s{Věta:} Běh algoritmu \astar{} odpovídá průběhu Dijkstrova algoritmu
-na~grafu redukovaném potenciálem~$-\psi$. Přesněji,
-pokud označíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
-v~synchronně běžícím Dijkstrovi, bude vždy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
+\s{Věta:} Běh algoritmu \astar{} odpovídá průběhu Dijkstrova algoritmu
+na~grafu redukovaném potenciálem~$-\psi$. Přesněji,
+pokud označíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
+v~synchronně běžícím Dijkstrovi, bude vždy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
 
 \proof
-Indukcí podle doby běhu obou algoritmů. Na počátku je $h^*(s)$ i $h(s)$ nulové
-a všechna ostatní $h^*$ a~$h$ jsou nekonečná, takže tvrzení platí. V~každém dalším
-kroku \astar{} vybere vrchol~$v$ s~nejmenťím $h^*(v) + \psi(v)$, coŞ je tentýŞ vrchol,
-kterĂ˝ vybere Dijkstra ($\psi(s)$ je stĂĄle stejnĂŠ).
-
-Uvažujme, co se stane během relaxace hrany $vw$: Dijkstra se pokusí snížit ohodnocení $h(w)$
-o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. UkĂĄĹžeme,
-že \astar{} udělá totéž:
+Indukcí podle doby běhu obou algoritmů. Na počátku je $h^*(s)$ i $h(s)$ nulové
+a všechna ostatní $h^*$ a~$h$ jsou nekonečná, takže tvrzení platí. V~každém dalším
+kroku \astar{} vybere vrchol~$v$ s~nejmenším $h^*(v) + \psi(v)$, což je tentýž vrchol,
+který vybere Dijkstra ($\psi(s)$ je stále stejné).
+
+Uvažujme, co se stane během relaxace hrany $vw$: Dijkstra se pokusí snížit ohodnocení $h(w)$
+o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. Ukážeme,
+že \astar{} udělá totéž:
 $$\eqalign{
 \delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
 &= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
 &= h^*(w) - h^*(v) - \ell(v,w).
 }$$
-Oba algoritmy tedy až na~posunutí dané potenciálem počítají totéž.
+Oba algoritmy tedy až na~posunutí dané potenciálem počítají totéž.
 \qed
 
-\s{Důsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ přípustný.
+\s{Důsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ přípustný.
 
-Například pro rovinnou mapu to heuristika daná euklidovskou vzdáleností~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splňuje:
-Přípustnost požaduje pro každou hranu $uv$ nerovnost
+Například pro rovinnou mapu to heuristika daná euklidovskou vzdáleností~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splňuje:
+Přípustnost požaduje pro každou hranu $uv$ nerovnost
 $\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
 tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
-JelikoĹž $\ell(u,v) \ge \varrho(u,v)$,
-stačí dokázat, že $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
-coĹž je ovĹĄem trojĂşhelnĂ­kovĂĄ nerovnost pro metriku~$\varrho$.
+Jelikož $\ell(u,v) \ge \varrho(u,v)$,
+stačí dokázat, že $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
+což je ovšem trojúhelníková nerovnost pro metriku~$\varrho$.
 
 \references
 \bye
-- 
2.39.5