3 \prednaska{13}{Nejkrat¹í cesty}{}
8 \def\astar{A\kern-0.15em *}
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èátkù. Základní algoritmy
12 pro hledání cest jsou nedílnou souèástí základních kursù programování
13 a algoritmù, my se budeme vìnovat zejména rùzným jejich vylep¹ením.
15 Uva¾ujme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena
16 {\I délkou} $\ell(e)\in{\bb R}$. Mno¾inì hran (tøeba sledu nebo cestì)
17 pak pøiøadíme délku rovnou souètu délek jednotlivých hran.
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ènì mnoho,
21 minimum v¾dy existuje). Pokud z~$u$ do~$v$ ¾ádná cesta nevede, polo¾íme
24 Obvykle se studují následující tøi problémy:
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ù.
36 Pøekvapivì, tak obecnì, jak jsme si uvedené problémy definovali, je neumíme
37 øe¹it v~polynomiálním èase: pro grafy, které mohou obsahovat hrany záporných
38 délek bez jakýchkoliv omezení, je toti¾ hledání nejkrat¹í cesty NP-tì¾ké
39 (lze na~nìj snadno pøevé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.
43 Na¹tìstí 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øihnout} a tím získat
45 sled, který není del¹í a~který má ménì hran. Ka¾dý nejkrat¹í sled tak
46 mù¾eme upravit na~stejnì 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èáteèního vrcholu,
49 nejkrat¹í sled ani neexistuje.
51 Navíc se nám bude hodit, ¾e ka¾dý prefix nejkrat¹í cesty je opìt nejkrat¹í
52 cesta. Jinými slovy pokud nìkterá z~nejkrat¹ích cest z~$u$ do~$v$ vede
53 pøes nìjaký vrchol~$w$, pak její èást z~$u$ do~$w$ je jednou z~nejkrat¹ích
54 cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í.)
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ìjaký podgraf grafu~$G$, který má tvar
58 stromu zakoøenìného v~$u$ a orientovaného smìrem od~koøene, a~platí pro nìj, ¾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.
62 \s{Pozorování:} Strom nejkrat¹ích cest v¾dy existuje.
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ìm¾ se nacházejí nejkrat¹í
67 cesty z~vrcholu~$u$ do vrcholù $v_1,\ldots,v_i$. Pro $i=1$ staèí 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èíme~$z$ poslední vrchol na~této cestì, který se je¹tì vyskytuje v~${\cal T}_{i-1}$.
71 Úsek nejkrat¹í cesty od~$z$ do~$v_i$ pak pøidáme do~${\cal T}_{i-1}$
72 a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
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èátku (v¹imnìte si, ¾e staèí
79 uvést pøedchùdce ka¾dého vrcholu), u~\apsp{} vydáme strom nejkrat¹ích cest
80 pro ka¾dý ze~zdrojových vrcholù.
82 Èasto se ov¹em uká¾e, ¾e podstatná èást problému se skrývá v~samotném
83 výpoètu vzdáleností a sestrojení pøedchùdcù je triviálním roz¹íøením algoritmu.
84 Budeme tedy obvykle jen poèítat vzdálenosti a samotnou rekonstrukci cest
85 ponecháme ètenáøi jako snadné cvièení.
87 \h{Relaxaèní algoritmus}
89 Zaènìme problémem \sssp{} a oznaème~$u$ výchozí vrchol. Vìt¹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ìjakého sledu z~$u$ do~$v$. Postupnì
92 toto ohodnocení upravují, a¾ se z~nìj stane vzdálenost $d(u,v)$ a algoritmus
95 Vhodnou operací pro vylep¹ování ohodnocení je takzvaná {\I relaxace.}
96 Vybereme si nìjaký vrchol~$v$ a pro v¹echny jeho sousedy~$w$ spoèítáme
97 $h(v) + \ell(v,w)$, tedy délku sledu, který vznikne roz¹íøení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øepí¹eme.
101 Abychom zabránili opakovaným relaxacím tého¾ vrcholu, které nic nezmìní,
102 budeme rozli¹ovat tøi stavy vrcholù: {\I nevidìn} (je¹tì jsme ho nenav¹tívili),
103 {\I otevøen} (zmìnilo se ohodnocení, èasem chceme relaxovat) a {\I uzavøen}
104 (u¾ jsme relaxovali a není potøeba znovu).
106 Ná¹ algoritmus bude fungovat následovnì:
109 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
110 \:$\<stav>(*)\leftarrow\<nevidìn>$, $\<stav>(u)\leftarrow\<otevøen>$.
111 \:Dokud existují otevøené vrcholy, opakujeme:
112 \::$v\leftarrow\hbox{libovolný otevøený vrchol}$.
113 \::$\<stav>(v)\leftarrow\<uzavøen>$.
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øen>$.
119 \:Vrátíme výsledek $d(u,v)=h(v)$ pro v¹echna~$v$.
122 Podobnì jako u~minimálních koster, i zde se jedná o~meta-algoritmus, proto¾e
123 v~kroku~4 nespecifikuje, který z~otevøených vrcholù vybírá. Pøesto
124 ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu
127 \s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak:
130 \:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu z~$u$ do~$v$.
131 \:$h(v)$ dokonce odpovídá délce nìjaké cesty z~$u$ do~$v$.
132 \:Algoritmus se v¾dy zastaví.
133 \:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$.
134 \:Po zastavení mají koneèné~$h(v)$ právì v¹echny uzavøené vrcholy.
135 \:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$.
141 \:Doká¾eme indukcí podle poètu krokù algoritmu.
142 \:Staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus.
143 \:Cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro ka¾dý~$v$, je koneènì mnoho.
144 \:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol,
145 který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran.
146 \:$h(v)$ nastavujeme na~koneènou hodnotu právì v~okam¾icích, kdy se vrchol stává otevøeným.
147 Ka¾dý otevøený vrchol je èasem uzavøen.
148 \:Kdyby tomu tak nebylo,
149 vyberme si ze~\uv{¹patných} vrcholù~$v$ takový, pro nìj¾ obsahuje nejkrat¹í cesta z~$u$ do~$v$
150 nejmen¹í mo¾ný poèet hran. Vrchol~$v$ je zajisté rùzný od~$u$, tak¾e má na~této cestì nìjakého
151 pøedchùdce~$w$. Pøitom~$w$ u¾ musí být ohodnocen správnì a relaxace, která mu toto ohodnocení
152 nastavila, ho musela prohlásit za~otevøený. Jen¾e ka¾dý otevøený vrchol je pozdìji uzavøen,
153 tak¾e~$w$ poté musel být je¹tì alespoò jednou relaxován, co¾ muselo sní¾it~$h(v)$ na správnou
158 \>Dokázali jsme tedy, ¾e meta-algoritmus pro libovolnou implementaci kroku~4
159 spoèítá správné vzdálenosti.
165 \:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9
166 pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$v$. Doka¾te, ¾e pøedchùdci
167 dosa¾itelných vrcholù budou tvoøit strom a ¾e tento strom bude stromem
168 nejkrat¹ích cest z~vrcholu~$u$.
169 \:Doka¾te, ¾e pro graf, v~nìm¾ je alespoò jeden záporný cyklus dosa¾itelný
170 z~poèáteèního vrcholu, se algoritmus nezastaví a ohodnocení v¹ech vrcholù
171 na cyklu postupnì klesnou libovolnì hluboko. Nedosa¾itelné záporné cykly
172 chod algoritmu samozøejmì nijak neovlivní.
175 \h{Bellmanùv-Fordùv-Mooreùv algoritmus}
177 Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM),
178 který lze v~øeèi na¹eho meta-algoritmu formulovat takto: Otevøené vrcholy
179 udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané
180 zaøazujeme na~konec). Co toto pravidlo zpùsobí?
182 \s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$.
185 Bìh algoritmu rozdìlí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ìhem $i$-té fáze.
189 V¹imneme si, ¾e na~konci $i$-té fáze je ka¾dé ohodnocení $h(v)$ shora omezeno
190 délkou nejkrat¹ího ze~sledù z~$u$ do~$v$, které mají nejvý¹e~$i$ hran. Fází je
193 Relaxace ka¾dého vrcholu pøitom trvá lineárnì se stupnìm vrcholu, tak¾e celá
194 fáze probìhne v~èase $\O(m)$. V¹echny fáze pak v~$\O(nm)$.
199 \:Uka¾te, ¾e asymptoticky stejné èasové slo¾itosti by dosáhl algoritmus,
200 který by vrcholy oèísloval $v_1,\ldots,v_n$ a opakovanì by je v~tomto
201 poøadí relaxoval tak dlouho, dokud by se ohodnocení mìnila.
202 \:Jak algoritmus upravit, aby v~$i$-té fázi spoèítal minimální délky sledù
204 \:Jak lze algoritmus BFM vyu¾ít k~nalezení záporného cyklu?
207 \h{Dijkstrùv algoritmus}
209 Pokud jsou v¹echny délky hran nezáporné, mù¾eme pou¾ít efektivnìj¹í pravidlo
210 pro výbìr vrcholu navr¾ené Dijkstrou \cite{dijkstra:mstandpath}. To øíká, ¾e v¾dy relaxujeme ten z~otevøených
211 vrcholù, jeho¾ ohodnocení je nejmen¹í.
213 \s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající
214 vzdálenosti od~$u$ a ka¾dý dosa¾itelný vrchol uzavøe právì jednou.
217 Indukcí doká¾eme, ¾e v~ka¾dém okam¾iku mají v¹echny uzavøené vrcholy ohodnocení
218 men¹í nebo rovné ohodnocením v¹ech otevøených vrcholù. Na~poèátku to jistì platí.
219 Nech» nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevøenými. Bìhem jeho
220 relaxace nemù¾eme ¾ádnou hodnotu sní¾it pod~$h(v)$, jeliko¾ v~grafu s~nezápornými
221 hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevøených vrcholù
222 tedy neklesne pod hodnotu tohoto novì uzavøeného. Hodnoty døíve uzavøených vrcholù
223 se nemohou nijak zmìnit.
226 Pøímoèará implementace Dijkstrova algoritmu by tedy poka¾dé v~èase $\O(n)$
227 vybrala otevøený vrchol s~nejmen¹ím ohodnocením, v~èase $\O(n)$ ho relaxovala
228 a toto by se opakovalo nejvý¹e $n$-krát. Algoritmus by tudí¾ dobìhl v~èase $\O(n^2)$,
229 co¾ je pro husté grafy zajisté optimální. Zkusíme nyní zrychlit výpoèet
232 V¹echny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, tak¾e úzkým hrdlem je
233 vybírání minima. Pou¾ijeme pro nìj vhodnou datovou strukturu, v~ní¾ budeme udr¾ovat
234 mno¾inu v¹ech otevøených vrcholù spolu s~jejich ohodnoceními. Od~datové struktury
235 potøebujeme, aby umìla operace \<Insert> (vlo¾ení vrcholu), \<ExtractMin> (nalezení
236 a smazání minima) a \<Decrease> (sní¾ení hodnoty vrcholu). První dvì operace pøitom
237 voláme nejvý¹e $n$-krát a operaci \<Decrease> nejvý¹e $m$-krát. Celý algoritmus
239 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
240 kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou èasové slo¾itosti jednotlivých operací
241 na~struktuøe o~nejvý¹e~$n$ prvcích (staèí amortizovanì).
243 \>Jaké mo¾nosti máme pro volbu struktury?
246 \:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
247 celkem tedy $\O(n^2)$.
248 \:{\I (binární) halda} -- v¹echny tøi operace umíme provést v~èase $\O(\log n)$, tak¾e celkem
249 $\O(m\log n)$. To je pro husté grafy hor¹í, pro øídké lep¹í.
250 \:{\I $k$-regulární halda} -- pokud haldu upravíme tak, ¾e ka¾dý prvek bude mít a¾ $k$ synù,
251 hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky smìrem nahoru,
252 co¾ je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ov¹em \<ExtractMin> potøebuje
253 zkoumat v¹echny syny ka¾dého nav¹tíveného prvku, tak¾e se zpomalí na $\O(k\log_k n)$.
255 Celková slo¾itost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba èleny se vyrovnají
256 pro $k=m/n$, èím¾ získáme $\O(m\log_{m/n} n)$. Èlen $\log_{m/n} n$ je pøitom $\O(1)$,
257 kdykoliv je $m\ge n^{1+\varepsilon}$ pro nìjaké~$\varepsilon>0$, tak¾e pro dostateènì
258 husté grafy jsme získali lineární algoritmus.
260 (V¹imnìte si, ¾e pro $m\approx n^2$ algoritmus zvolí $k\approx n$, tak¾e halda degeneruje
261 na jediné patro, tedy na pole, které se opravdu ukázalo být optimální volbou pro husté grafy.)
262 \:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má slo¾itost
263 $\O(\log n)$ [v¹e amortizovanì]. Dijkstrùv algoritmus proto dobìhne v~èase $\O(m + n\log n)$.
264 To je lineární pro grafy s~hustotou $\Omega(\log n)$.
265 \:{\I Monotónní haldy} -- mù¾eme pou¾ít nìjakou jinou haldu, která vyu¾ívá toho,
266 ¾e posloupnost odebíraných prvkù je neklesající. Pro celá èísla na~\hbox{RAMu} to mù¾e
267 být napøíklad Thorupova halda \cite{thorup:queue} se slo¾itostí $\O(\log\log n)$ u~operace \<ExtractMin>
268 a $\O(1)$ u~ostatních operací. Dijkstra tedy bì¾í v~$\O(m + n\log\log n)$.
269 \:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápìtí.
275 \:Najdìte pøíklad grafu se zápornými hranami (ale bez záporných cyklù),
276 na~kterém Dijkstrùv algoritmus sel¾e.
277 \:Rozmyslete si, ¾e pokud nevyu¾ijeme nìjaké speciální vlastnosti èísel (celoèíselnost,
278 omezený rozsah), je mez $\O(m+n\log n)$ nejlep¹í mo¾ná, proto¾e Dijkstrovým algoritmem
279 mù¾eme tøídit $n$-tici èísel. Thorup dokonce dokázal \cite{thorup:equiv}, ¾e z~ka¾dého tøídícího algoritmu
280 se slo¾itostí $\O(nT(n))$ mù¾eme odvodit haldu se slo¾itostí mazání $\O(T(n))$.
281 \:Jsou-li délky hran celoèíselné, mù¾eme se na Dijkstrùv algoritmus dívat i takto:
282 Pøedstavme si, ¾e ka¾dou hranu nahradíme cestou tvoøenou pøíslu¹ným poètem hran jednotkové délky
283 a na vzniklý neohodnocený graf spustíme prohledávání do~¹íøky. To samozøejmì vydá
284 správný výsledek, ale pomìrnì pomalu, proto¾e bude vìt¹inu èasu trávit posouváním
285 vlny \uv{uvnitø} pùvodních hran. Mù¾eme si tedy pro ka¾dou pùvodní hranu naøídit
286 \uv{budík}, který nám øekne, za~kolik posunutí vlny dospìjeme na~její konec.
287 Doka¾te, ¾e tento algoritmus je ekvivalentní s~Dijkstrovým.
290 \h{Celoèíselné délky}
292 Uva¾ujme nyní grafy, v~nich¾ jsou v¹echny délky hran nezáporná celá èísla omezená
293 nìjakou konstantou~$L$. V¹echny vzdálenosti jsou tedy omezeny èíslem~$nL$, tak¾e
294 nám staèí datová struktura schopná uchovávat takto omezená celá èísla.
296 Pou¾ijeme jednoduchou pøihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
297 jeho $i$-tý prvek bude obsahovat seznam vrcholù, jejich¾ ohodnocení je rovno~$i$.
298 Operace \<Insert> a \<Decrease> zvládneme v~konstantním èase, budeme-li si u~ka¾dého
299 prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potøebuje najít první
300 neprázdnou pøihrádku, ale jeliko¾ víme, ¾e posloupnost odebíraných minim je monotónní,
301 staèí hledat od místa, kde se hledání zastavilo minule. V¹echna hledání pøihrádek
302 tedy zaberou dohromady $\O(nL)$ a celý Dijkstrùv algoritmus bude trvat $\O(nL + m)$.
304 Prostorová slo¾itost $\O(nL+m)$ je nevalná, ale mù¾eme ji jednoduchým trikem
305 sní¾it: V¹imneme si, ¾e v¹echna koneèná ohodnocení vrcholù nemohou být vìt¹í
306 ne¾ aktuální minimum zvìt¹ené o~$L$. Jinými slovy v¹echny neprázdné pøihrádky
307 se nacházejí v~úseku pole dlouhém~$L+1$, tak¾e staèí indexovat modulo~$L+1$.
308 Pouze si musíme dávat pozor, abychom správnì poznali, kdy se struktura
309 vyprázdnila, co¾ zjistíme napøíklad pomocí poèítadla otevøených vrcholù. Èas si
310 asymptoticky nezhor¹íme, prostor klesne na~$\O(L+m)$.
312 Podobný trik mù¾eme pou¾ít i pro libovolnou jinou datovou strukturu: rozsah èísel
313 rozdìlíme na~\uv{okna} velikosti~$L$ (v~$i$-tém oknì jsou èísla $iL,\ldots,(i+1)L-1$).
314 V~libovolné chvíli mohou tedy být neprázdná nejvý¹e dvì okna. Staèí nám proto
315 poøídit si dvì struktury pro ukládání èísel v~rozsahu $0,\ldots,L-1$ -- jedna
316 z~nich bude reprezentovat aktuální okno (to, v~nìm¾ le¾elo minulé minimum),
317 druhá okno bezprostøednì následující. Minimum ma¾eme z~první struktury; pokud
318 u¾ je prázdná, obì struktury prohodíme. Operace \<Insert> podle hodnoty urèí,
319 do~které struktury se má vkládat. S~operací \<Decrease> je to slo¾itìj¹í --
320 hodnota z~vy¹¹í struktury mù¾e pøeskoèit do té ni¾¹í, ale v~takovém pøípadì
321 ji ve~vy¹¹í struktuøe vyma¾eme (to je \<Decrease> na $-\infty$ následovaný
322 \<ExtractMin>em) a do~té ni¾¹í vlo¾íme. To se ka¾dému prvku mù¾e pøihodit nejvý¹e
323 jednou, tak¾e stále platí, ¾e se ka¾dý prvek úèastní $\O(1)$ vlo¾ení a $\O(1)$
326 Ukázali jsme tedy, ¾e pro na¹e potøeby postaèuje struktura schopná uchovávání
327 èísel men¹ích nebo rovných~$L$.
329 Nabízí se pou¾ít van Emde-Boasùv strom z~kapitoly o~výpoèetních modelech.
330 Ten dosahuje slo¾itosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
331 operaci \<Decrease> musíme pøekládat na \<Delete> a \<Insert>. Celková
332 slo¾itost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, pøièem¾ èas~$L$
333 spotøebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
334 viz zmínìná kapitola).
336 Vra»me se ale je¹tì k~vyu¾ití pøihrádek\dots
338 \h{Víceúrovòové pøihrádky}
340 Podobnì jako u~tøídìní èísel, i~zde se vyplácí stavìt pøihrádkové struktury
341 víceúrovòovì (pùvodnì popsáno Goldbergem a Silversteinem \cite{goldberg:mlb}).
342 Jednotlivé hodnoty budeme zapisovat v~soustavì o~základu~$B$,
343 který zvolíme jako nìjakou mocninu dvojky, abychom mohli s~èíslicemi tohoto
344 zápisu snadno zacházet pomocí bitových operací. Ka¾dé èíslo tedy zabere nejvý¹e
345 $d=1+\lfloor\log_B L\rfloor$ èíslic; pokud bude krat¹í, doplníme ho zleva nulami.
347 Nejvy¹¹í patro struktury bude tvoøeno polem $B$~pøihrádek, v~$i$-té z~nich
348 budou ulo¾ena ta èísla, jejich¾ èíslice nejvy¹¹ího øádu je rovna~$i$. Za~{\I aktivní}
349 prohlásíme tu pøihrádku, která obsahuje aktuální minimum. Pøihrádky s~men¹ími
350 indexy jsou prázdné a zùstanou takové a¾ do~konce výpoètu, proto¾e halda
351 je monotónní. Pokud v~pøihrádce obsahující minimum bude více prvkù, budeme
352 ji rozkládat podle druhého nejvy¹¹ího øádu na dal¹ích~$B$ pøihrádek atd.
353 Celkem tak vznikne a¾~$d$ úrovní.
355 \>Struktura bude obsahovat následující data:
358 \:Parametry $L$, $B$ a~$d$.
359 \:Pole úrovní (nejvy¹¹í má èíslo~$d-1$, nejni¾¹í~0), ka¾dá úroveò je buïto prázdná
360 (a pak jsou prázdné i~v¹echny ni¾¹í), nebo obsahuje pole~$U_i$ o~$B$ pøihrádkách
361 a v~ka¾dé z~nich seznam prvkù. Pole úrovní pou¾íváme jako zásobník, udr¾ujeme
362 si èíslo nejni¾¹í neprázdné úrovnì.
363 \:Hodnotu~$\mu$ pøedchozího odebraného minima.
366 Operace \<Insert> vlo¾í hodnotu do~nejhlub¹í mo¾né pøihrádky. Podívá se tedy
367 na~nejvy¹¹í úroveò: pokud hodnota patøí do pøihrádky, která není aktivní, vlo¾í
368 ji pøímo. Jinak pøejde o~úroveò ní¾e a zopakuje stejný postup. To v¹e lze provést
369 v~konstantním èase: staèí se podívat, jaký je nejvy¹¹í jednièkový bit ve~{\sc xor}u
370 nové hodnoty s~èíslem~$\mu$ (opìt viz kapitola o~výpoèetních modelech), a tím zjistit
371 èíslo úrovnì, kam hodnota patøí.
373 Pokud chceme provést \<Decrease>, odstraníme hodnotu z~pøihrádky, ve~které se
374 právì nachází (polohu si mù¾eme u~ka¾dé hodnoty pamatovat zvlá¹»), a znovu ji
377 Vìt¹inu práce samozøejmì pøenecháme funkci \<ExtractMin>. Ta zaène prohledávat
378 nejni¾¹í obsazenou úroveò od~aktivní pøihrádky dál (to, která pøihrádka je na
379 které úrovni aktivní, poznáme z~èíslic hodnoty~$\mu$). Pokud pøihrádky na~této
380 úrovni dojdou, prázdnou úroveò zru¹íme a pokraèujeme o~patro vý¹e.
382 Jakmile najdeme neprázdnou pøihrádku, nalezneme v~ní minimum a to se stane novým~$\mu$.
383 Pokud v~pøihrádce nebyly ¾ádné dal¹í prvky, skonèíme. V~opaèném pøípadì zbývající
384 prvky rozprostøeme do~pøihrádek na~bezprostøednì ni¾¹í úrovni, kterou tím zalo¾íme.
386 Èas strávený hledáním minima mù¾eme rozdìlit na~nìkolik èástí:
389 \:$\O(B)$ na inicializaci nové úrovnì -- to naúètujeme prvku, který jsme
391 \:hledání neprázdných pøihrádek -- prozkoumání ka¾dé prázdné pøihrádky
392 naúètujeme jejímu vytvoøení, co¾ se rozpustí v~$\O(B)$ na inicializaci
394 \:zru¹ení úrovnì -- opìt naúètujeme jejímu vzniku;
395 \:rozhazování prvkù do pøihrádek -- jeliko¾ prvky v~hierarchii pøihrádek
396 putují bìhem operací pouze doleva a dolù (jejich hodnoty se nikdy nezvìt¹ují),
397 klesne ka¾dý prvek nejvý¹e~$d$-krát, tak¾e staèí, kdy¾ na v¹echna rozhazování
398 pøispìje èasem $\O(d)$.
401 \>Staèí tedy, aby ka¾dý prvek pøi \<Insert>u zaplatil èas $\O(B+d)$ a jak \<Decrease>,
402 tak \<ExtractMin> budou mít konstantní amortizovanou slo¾itost. Dijkstrùv
403 algoritmus pak pobì¾í v~$\O(m + n(B+d))$.
405 Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
406 Vhodná volba je $B=\log L/\log\log L$. Pøi ní platí
408 {\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
409 = {\log L\over \log\log L - \log\log\log L} = \Theta(B).
411 Tehdy Dijkstra vydá výsledek v~èase $\O(m + n\cdot{\log L\over\log\log L})$.
413 \h{HOT Queue -- kombinace pøihrádek s~haldou}
415 Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách
416 platíme pøíli¹ mnoho za~úrovnì, ve~kterých se za~dobu jejich existence objeví jen malé
417 mno¾ství prvkù. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~spoleèné haldy.
418 Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. My si pøedvedeme její upravenou
419 variantu (v~té pùvodní se skrývá nìkolik chyb).
421 Poøídíme si haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající,
422 kolik prvkù z~této úrovnì jsme ulo¾ili do~haldy. Dokud toto poèítadlo nepøeroste nìjaký
423 parametr~$H$, pøihrádky nebudeme zakládat a prvky poputují do~haldy. Èas $\O(B)$ na
424 zalo¾ení úrovnì a její procházení proto mù¾eme rozpoèítat mezi~$H$ prvkù, které se musely
425 na~dané úrovni objevit, ne¾ byla rozpøihrádkována. (Pov¹imnìte si, ¾e poèítadlo nikdy
426 nesni¾ujeme, pouze ho vynulujeme, kdy¾ je úroveò zru¹ena. Proto vùbec nemusí odpovídat
427 skuteènému poètu prvkù z~pøíslu¹né úrovnì, které jsou právì ulo¾eny v~haldì. To ov¹em
428 vùbec nevadí -- poèítadlo pouze hlídá, aby se úroveò nevytvoøila pøíli¹ brzy, tedy abychom
429 mìli dost prvkù k~rozúètování èasu.)
431 Promìnnou~$\mu$ necháme ukazovat na~místo, kde jsme se pøi hledání minima v~pøihrádkách
432 zastavili. Souèasné globální minimum struktury mù¾e být ni¾¹í, nachází-li se minimum
433 zrovna v~haldì. Stále je v¹ak zaruèeno, ¾e pøed~$\mu$ se nenachází ¾ádná
436 Operace budou fungovat takto:
440 \:Spoèítáme, do~které úrovnì~$i$ má prvek padnout (bitovými operacemi).
441 \:Pokud je poèítadlo této úrovnì men¹í ne¾~$H$, zvý¹íme ho, vlo¾íme prvek do~haldy a skoèíme.
442 \:Nebyly-li je¹tì pro tuto úroveò zalo¾eny pøihrádky, vyrobíme prázdné.
443 \:Vlo¾íme prvek do~pøíslu¹né pøihrádky.
448 \:Pokud se prvek nachází v~haldì (to si u~ka¾dého prvku pamatujeme), provedeme
449 \<Decrease> v~haldì a skonèíme.
450 \:Sma¾eme prvek z~jeho pøihrádky a provedeme \<Insert> s~novou hodnotou.
455 \:Dokud je~$\mu$ men¹í ne¾ aktuální minimum haldy, opakujeme:
456 \::Najdeme pøihrádku odpovídající hodnotì~$\mu$.
457 \::Je-li tato pøihrádka prázdná, pøejdeme na~dal¹í (upravíme~$\mu$). Jsme-li na konci úrovnì,
458 zru¹íme ji, vynulujeme její poèítadlo a pokraèujeme o~úroveò vý¹.
459 \::Není-li prázdná, rozprostøeme ji pøihrádku o~úroveò ní¾ (stejným zpùsobem jako pøi \<Insert>u,
460 tak¾e prvních~$H$ prvkù vlo¾íme do~haldy).
461 \:Sma¾eme minimum z~haldy a vrátíme ho jako výsledek.
464 \>Pustíme se do~analýzy slo¾itosti. Jako parametry si zvolíme poèet hladin~$d$ (tak¾e
465 poèet pøihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
467 Nejprve si v¹imneme, ¾e ne¾ poèítadlo nìjaké úrovnì vynulujeme, jsou bezpeènì
468 z~haldy pryè v¹echny prvky patøící do~této úrovnì. Celkem se tedy v~haldì
469 vyskytuje nejvý¹e $\O(dH)$ prvkù. \<ExtractMin> v~haldì proto trvá $\O(\log(dH))$,
470 ostatní haldové operace $\O(1)$.
472 Nyní rozúètujeme èas operací mezi jednotlivé prvky (opìt si v¹e pøedplatíme
473 v~\<Insert>u a ostatní operace pobì¾í v~amortizovanì konstantním èase):
476 \:Ka¾dý prvek mù¾e být nejvý¹e jednou za~dobu svého ¾ivota vlo¾en do~haldy
477 a nejvý¹e jednou z~ní vyjmut. Na~obojí dohromady pøispìje $\O(\log dH)$.
478 \:Prvek se úèastní nejvý¹e~$d$ pøehození do~ni¾¹í úrovnì. Pokud byl pøihozen
479 do~haldy, u¾ tam setrvá, jinak poka¾dé zaplatí $\O(1)$ za~zaøazení do~pøihrádky,
480 celkem tedy $\O(d)$ na prvek.
481 \:Vytvoøení, projití a smazání pøihrádek na~jedné úrovni nastane a¾ tehdy, co bylo
482 $H$~prvkù patøících do~této úrovnì vlo¾eno do~haldy. Staèí tedy, aby ka¾dý
483 prvek pøispìl èasem $\O(B/H) = \O(L^{1/d}/H)$.
486 \>Ka¾dý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
487 Pojïme najít nastavení parametrù, které tento výraz minimalizuje.
488 Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
489 Celý výraz tím zjednodu¹íme na $\O(d + \log\,(L^{1/d}/d))$ =
490 $\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sèítance volbou
491 $d=\sqrt{\log L}$ vyrovnáme.
493 HOT Queue tedy zvládne \<Insert> s~amortizovanou èasovou slo¾itostí $\O(\sqrt{\log L})$
494 a ostatní operace v~èase amortizovanì konstantním. Pou¾ijeme-li tuto strukturu
495 v~Dijkstrovì algoritmu, spoète vzdálenosti v~èase $\O(m + n\sqrt{\log L})$.
497 \h{Dinicùv algoritmus}
499 Zajímavé vylep¹ení Dijkstrova algoritmu navrhl Dinic. V¹iml si, ¾e pokud
500 je ka¾dá hrana dlouhá alespoò~$\delta$, mù¾eme uzavírat nejen
501 vrchol s~minimálním ohodnocením~$\mu$, ale i v¹echny s~ohodnocením
502 men¹ím ne¾ $\mu+\delta$.
504 Pro takto upravený Dijkstrùv algoritmus bude stále platit, ¾e pøi uzavírání
505 vrcholu odpovídá ohodnocení skuteèné vzdálenosti, tak¾e uzavøené vrcholy ji¾
506 nejsou znovu otevírány.
508 O~monotonii vzdáleností jsme sice pøi¹li, ale v~pøihrádkové struktuøe nebo
509 haldì mù¾eme klíèe nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
510 Tyto hodnoty se toti¾ chovají monotónnì a vrcholy se stejným $h'(v)$ mù¾eme
513 Kteroukoli z~popsaných pøihrádkových struktur mù¾eme tedy pou¾ít, pouze
514 v~rozboru èasové slo¾itosti nahradíme~$L$ výrazem $L/\delta$. Tento pøístup
515 pøitom funguje i pro neceloèíselné kapacity, pouze potøebujeme mít pøedem
516 k~dispozici netriviální dolní odhad na~délky v¹ech hran.
520 Vidìli jsme, ¾e v~grafech s~nezápornými délkami hran se nejkrat¹í cesty
521 hledají snáze. Nabízí se nalézt nìjakou transformaci, která by
522 dovedla délky hran upravit tak, aby byly nejkrat¹í cesty zachovány (samozøejmì
523 ne jejich délky, ale alespoò to, které cesty jsou nejkrat¹í). Nabízí se
524 následující fyzikální inspirace:
526 \s{Definice:} {\I Potenciál} budeme øíkat libovolné funkci $\psi: V\rightarrow {\bb R}$.
527 Pro ka¾dý potenciál zavedeme {\I redukované délky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
528 Potenciál nazveme {\I pøípustný,} pokud ¾ádná hrana nemá zápornou redukovanou délku.
530 \s{Pozorování:} Pro redukovanou délku libovolné cesty~$P$ z~$u$ do~$v$ platí: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.
533 Nech» cesta~$P$ prochází pøes vrcholy $u=w_1,\ldots,w_k=v$. Potom:
535 \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).
537 Tato suma je ov¹em teleskopická, tak¾e z~ní zbude
539 \sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k) = \ell(P) + \psi(u) - \psi(v).
544 \s{Dùsledek:} Potenciálovou redukcí se délky v¹ech cest mezi~$u$ a~$v$
545 zmìní o~tuté¾ konstantu, tak¾e struktura nejkrat¹ích cest zùstane nezmìnìna.
547 Zbývá pøijít na~to, kde si obstarat nìjaký pøípustný potenciál. Pøidejme do~grafu
548 nový vrchol~$z$, pøiveïme z~nìj hrany nulové délky do~v¹ech ostatních vrcholù
549 a~oznaème~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál
550 pøípustný, musí pro ka¾dou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
551 Tuto nerovnost mù¾eme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, èili
552 $d(z,u) + \ell(u,v) \ge d(z,v)$, co¾ je ale obyèejná trojúhelníková nerovnost
553 pro vzdálenost v~grafu, která jistì platí.
555 Jedním výpoètem nejkrat¹ích cest v~grafu se zápornými hranami (tøeba algoritmem BFM)
556 tedy doká¾eme spoèítat potenciál, který nám poslou¾í k~redukci v¹ech hran na~nezáporné
557 délky. To nám samozøejmì nepomù¾e, chceme-li jednorázovì hledat nejkrat¹í cestu,
558 ale mù¾e nám to výraznì zjednodu¹it dal¹í, slo¾itìj¹í práci s~grafem. Jak uvidíme
559 v~pøí¹tí kapitole, mù¾eme tak napøíklad nalézt vzdálenosti mezi v¹emi dvojicemi
560 vrcholù v~èase $\O(nm + n^2\log n)$.
562 Na~závìr tohoto oddílu doká¾eme jedno pomocné tvrzení o~potenciálech, které
563 nám pomù¾e v~konstrukci algoritmù typu \ppsp:
565 \s{Lemma:} Pokud $f$ a~$g$ jsou pøípustné potenciály, pak jsou jimi i:
567 \:konvexní kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolné $\alpha,\beta\ge 0, \alpha+\beta=1$;
572 \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)$.
573 Jednotlivé èásti tvrzení doká¾eme takto:
575 \:Pokud obì strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$
576 konstantou~$\beta$ a obì nerovnosti seèteme, dostaneme:
578 (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)),
580 co¾ je pøesnì po¾adovaná nerovnost pro pøípustnost funkce $\alpha f+\beta g$.
581 \:Oznaème $h := \min(f,g)$. Nech» bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$,
582 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)$.
583 Tehdy si staèí v¹imnout, ¾e $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, tak¾e
584 potenciál~$h$ je pøípustný.
585 \:Doká¾eme analogicky.
589 \h{Algoritmy pro problém typu \ppsp}
591 Zamìøme se nyní na~pøípad, kdy chceme hledat nejkrat¹í cesty mezi zadanou dvojicí
592 vrcholù $s$,~$t$. Obvykle se i v~této situaci pou¾ívají algoritmy \sssp{} (SSSP) a v~obecném
593 pøípadì ani není efektivnìj¹í øe¹ení známo. Existuje ov¹em velké mno¾ství heuristik, kterými
594 lze obvykle výpoèet zrychlit. Nìkteré z~nich si pøedvedeme na Dijkstrovì algoritmu.
596 Dijkstrùv algoritmus ve~své klasické podobì neví vùbec nic o~cílovém vrcholu a
597 prohledá celý graf. Hned se nabízí vyu¾ít toho, ¾e od~okam¾iku uzavøení
598 kteréhokoliv vrcholu se ji¾ jeho ohodnocení nezmìní. Pokud tedy uzavøeme cílový
599 vrchol, mù¾eme se zastavit.
601 Jakou èást grafu prohledáváme teï? V~metrice dané vzdálenostmi v~grafu je to nejmen¹í
602 koule se støedem ve~vrcholu~$u$, která obsahuje nejkrat¹í cestu (dobøe se to
603 pøedstavuje na~hledání v~silnièní síti na~rovinné mapì).
605 Také mù¾eme spustit prohledávání z~obou koncù zároveò, tedy zkombinovat hledání
606 od~$s$ v~pùvodním grafu s~hledáním od~$t$ v~grafu s~obrácenou orientací hran.
607 Oba postupy mù¾eme libovolnì støídat a zastavíme se v~okam¾iku, kdy jsme jeden
608 vrchol uzavøeli v~obou smìrech. Pozor ov¹em na to, ¾e souèet obou ohodnocení
609 tohoto vrcholu nemusí být roven $d(v,u)$ -- zkuste vymyslet protipøíklad.
610 Nejkrat¹í cesta je¹tì mù¾e vypadat tak, ¾e pøechází po nìjaké hranì mezi vrcholem
611 uzavøeným v~jednom smìru a vrcholem uzavøeným ve~smìru druhém (ponechme bez dùkazu).
612 Staèí tedy bìhem relaxace zjistit, zda je konec hrany uzavøený v~opaèném
613 smìru prohledávání, a~pokud ano, zapoèítat cestu do~prùbì¾ného minima.
615 Obousmìrný Dijkstrùv algoritmus projde sjednocení nìjaké koule okolo~$s$ s~nìjakou
616 koulí okolo~$t$, které obsahuje nejkrat¹í cestu. Prùmìry koulí pøitom závisí na tom,
617 jak budeme bìhem výpoètu støídat oba smìry prohledávání. V~nejhor¹ím pøípadì samozøejmì
618 mù¾eme prohledat celý graf.
620 \h{Algoritmus \astar}
622 V~umìlé inteligenci se èasto pro hledání nejkrat¹í cesty v~rozsáhlých grafech
623 (obvykle stavových prostorech úloh) pou¾ívá algoritmus nazývaný~\astar{} \cite{hart:astar}.
624 Jedná se o~modifikaci Dijkstrova algoritmu, která vyu¾ívá heuristickou funkci
625 pro dolní odhad vzdálenosti do~cíle; oznaème si ji $\psi(v)$. V~ka¾dém kroku pak uzavíra
626 vrchol~$v$ s~nejmen¹ím mo¾ným souètem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.
628 Intuice za tímto algoritmem je jasná: pokud víme, ¾e nìjaký vrchol je blízko
629 od~poèátaèního vrcholu~$s$, ale bude z~nìj urèitì daleko do cíle~$t$, zatím ho
630 odlo¾íme a budeme zkoumat nadìjnìj¹í varianty.
632 Heuristika se pøitom volí podle konkrétního problému -- napø. hledáme-li cestu
633 v~mapì, mù¾eme pou¾ít vzdálenost do~cíle vzdu¹nou èarou.
635 Je u~tohoto algoritmu zaruèeno, ¾e v¾dy najde nejkrat¹í cestu? Na to nám dá odpovìï
638 \s{Vìta:} Bìh algoritmu \astar{} odpovídá prùbìhu Dijkstrova algoritmu
639 na~grafu redukovaném potenciálem~$-\psi$. Pøesnìji,
640 pokud oznaèíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
641 v~synchronnì bì¾ícím Dijkstrovi, bude v¾dy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
644 Indukcí podle doby bìhu obou algoritmù. Na poèátku je $h^*(s)$ i $h(s)$ nulové
645 a v¹echna ostatní $h^*$ a~$h$ jsou nekoneèná, tak¾e tvrzení platí. V~ka¾dém dal¹ím
646 kroku \astar{} vybere vrchol~$v$ s~nejmen¹ím $h^*(v) + \psi(v)$, co¾ je tentý¾ vrchol,
647 který vybere Dijkstra ($\psi(s)$ je stále stejné).
649 Uva¾ujme, co se stane bìhem relaxace hrany $vw$: Dijkstra se pokusí sní¾it ohodnocení $h(w)$
650 o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. Uká¾eme,
651 ¾e \astar{} udìlá toté¾:
653 \delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
654 &= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
655 &= h^*(w) - h^*(v) - \ell(v,w).
657 Oba algoritmy tedy a¾ na~posunutí dané potenciálem poèítají toté¾.
660 \s{Dùsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ pøípustný.
662 Napøíklad pro rovinnou mapu to heuristika daná euklidovskou vzdáleností~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splòuje:
663 Pøípustnost po¾aduje pro ka¾dou hranu $uv$ nerovnost
664 $\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
665 tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
666 Jeliko¾ $\ell(u,v) \ge \varrho(u,v)$,
667 staèí dokázat, ¾e $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
668 co¾ je ov¹em trojúhelníková nerovnost pro metriku~$\varrho$.