3   Vzdálenost a nejkratší cesty v grafech
Při procházení grafu je někdy prostá informace o souvislosti dostačující, ale většinou bychom rádi věděli i jak je z jednoho vrcholu do druhého daleko . . .
V jednodušším případě se při zjišťování grafové vzdálenosti díváme jen na minimální počet prošlých hran z vrcholu do vrcholu. V obecném případě však při určování vzdálenosti bereme do úvahy délky jednotlivých hran podél cesty (tyto délky musí být nezáporné!).
Stručný přehled lekce
• Vzdálenost v grafech a její vlastnosti.
• Dynamický výpočet metriky grafu (Floyd-Warshall).
• Dijkstrův algoritmus pro nejkratší (ohodnocenou) cestu v grafu.
• Některé pokročilé myšlenky plánování cest.
Petr Hliněný,   Fl MU Brno, 2011
1/17
Fl: MA010: Vzdálenost v grafech
3.1   Vzdálenost v grafu
Zopakujme si, že sledem délky n v grafu G rozumíme posloupnost vrcholů a hran
vo, ei, «i, ě2, «2, • • •, e„, «„, ve které hrana     má koncové vrcholy Ví-i, Ví.
Definice 3.1. Vzdálenost da(u,v) dvou vrcholů u,v v grafu G
je dána délkou nejkratšího sledu mezi u a v v G.
Pokud sled mezi w,t> neexistuje, je vzdálenost da(u,v) — oo. □
Neformálně řečeno, vzdálenost mezi «, v je rovna nejmenšímu počtu hran, které musíme projít, pokud se chceme dostat z « do «. Speciálně do{u,u) = 0.
Uvědomme si, že nejkratší sled je vždy cestou (vrcholy se neopakují) - Věta 2.2.
Fakt: V neorientovaném grafu je vzdálenost symetrická, tj. dc(u,v) — dc(v,u). □
Lema 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost:
\fu,v,w g V (G) :   dc(u,v) + dc(v,w) > dc(u,w).
Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky dc(u,v) mezi u, v lze navázat sled délky dc(v, w) mezi v, w, čímž vznikne sled délky dc(u, v) + dc(v,w) mezi u,w. Skutečná vzdálenost mezi u,w pak už může být jen menší. C
Petr Hliněný,   Fl MU Brno, 2011
2/17
Fl: MA010: Vzdálenost v grafech
Základní zjištění vzdálenosti
Věta 3.3. Necht u,v,w jsou vrcholy souvislého grafu G takové, že dc(u,v) < dc(u, w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w. □
Důkaz. Postupujeme indukcí podle vzdálenosti dc(u,v): Pro dc(u,v) — 0, tj. u — v je tvrzení jasné - vrchol u jako počátek prohledávání byl nalezen první. Proto nechť dc(u,v) — d > 0 a označme v' souseda vrcholu v bližšího k u, tedy dc(u,v') — d— 1. Obdobně uvažme libovolného souseda w' vrcholu w. Pak
dc(u, w') > dc(u, w) — 1 > dc(u, v) — 1 — dc(u, v1).
a tudíž vrchol v' byl nalezen v prohledávání do šířky dříve než vrchol w' podle indukčního předpokladu. To znamená, že v' se dostal do fronty úschovny dříve než w'. Proto sousedé v' (mezi nimiž je v, ale ne w neboť v'w není hranou) jsou při pokračujícím prohledávání také nalezeni dříve než w coby soused w'. C
Důsledek 3.4. Algoritmus procházení grafu do šířky lze použít pro výpočet grafové vzdálenosti z daného vrcholu u. :
Důsledek 3.4 „funguje" jen pro vzdálenosti s jednotkovou délkou všech hran. My si dále ukážeme obecnější Dijkstrův algoritmus, který obdobným postupem počítá nejkratší vzdálenost při libovolně kladně ohodnocených délkách hran.
Petr Hliněný,   Fl MU Brno, 2011
3/17
Fl: MA010: Vzdálenost v grafech
Některé další pojmy
Definice 3.5.   Mějme graf G. Definujeme (vzhledem k G) následující pojmy a značení:
• Excentricita vrcholu exc(t>) je nejdelší vzdálenost z f do jiného vrcholu grafu;
exc(v) = maxxev(G) dG{v,x). □
• Průměr d ia m (G) grafu G je největší excentricita jeho vrcholů, naopak poloměr rad(G) grafu G je nejmenší excentricita jeho vrcholů. □
• Centrem grafu je množina vrcholů U C V (G) takových, jejichž excentricita je rovna poloměru rad(G). □
• Steinerová vzdálenost mezi vrcholy libovolné podmnožiny W C V (G) je rovna minimálnímu počtu hran souvislého podgrafu v G obsahujícího všechny vrcholy W.
Petr Hliněný,   Fl MU Brno, 2011
4/ 17
Fl: MA010: Vzdálenost v grafech
3.2   Výpočet metriky
Definice: Metrikou grafu myslíme soubor vzdáleností mezi všemi dvojicemi vrcholů grafu. Jinak řečeno, metrikou grafu G je matice (dvourozměrné pole) d[,], ve kterém prvek d [i, j] udává vzdálenost mezi vrcholy i a j. □
Metoda 3.6. Dynamický výpočet metriky skládáním cest
v grafu G na množině vrcholů V(G) — {t>o, f i, ■ ■ ■, v n-i}-
• Na počátku nechť d[i,j] udává 1 (případně délku hrany {ví,vj}), nebo oc pokud hrana mezi í,j není.
• Po kroku t > 0 nechť platí, že d[i, j] udává délku nejkratšího sledu mezi Vi,Vj, který užívá pouze vnitřní vrcholy z množiny {t>o, t>i,..., t>t-i} (prázdné v t — 0).
• Při přechodu z kroku t na následující krok í+1 upravujeme vzdálenost pro každou dvojici vrcholů Ví,vj - jsou vždy pouhé dvě možnosti:
- Bud' je sled délky d[i,j] z předchozího kroku t stále nejlepší (tj. nově povolený vrchol vt nám nepomůže),
- nebo sled vylepšíme spojením přes nově povolený vrchol vt, čímž získáme menší vzdálenost d [i, t] +d [t, j ] —>• d [i, j ].
Věta 3.7. Metoda 3.6 v poli d[i, j] správně vypočte vzdálenost mezi vrcholy Ví,vj .
Petr Hliněný,   Fl MU Brno, 2011
5/17
Fl: MA010: Vzdálenost v grafech
Poznámka: V implementaci pro symbol co použijeme velkou konstantu, třeba MAX_INT/2.
Algoritmus 3.8. Výpočet metriky grafu; Floyd-Warshall
vstup < matice sousednosti G 1,1 grafu na N vrcholech (číslovaných 0. . . N-lj, kde G [i, j ] =1 pro hranu mezi i, j a G [i, j ] =0 jinak;
for (i=0; i<N; i++) for (j=0; j<N; j++)
d[i,j] = (i==j?0:  (G[i,j]? 1: MAX_INT/2)); for (t=0; t<N; t++) {
for (i=0; i<N; i++) for (j=0; j<N; j++) d[i,j] = min(d[i,j], d[i,t]+d[t,j]);
}
výstup ' Matice vzdálenostíd[,] '; c
Algoritmus 3.8 je implementačně velmi jednoduchý a provede zhruba N3 kroků pro výpočet celé metriky.
Jeho jedinou (ale velkou) nevýhodou je, že vzdálenosti mezi všemi dvojicemi vrcholů je třeba počítat najednou. V praktických situacích však obvykle požadujeme zjištění vzdálenosti mezi jedinou dvojicí vrcholů, a pak celý zbytek výpočtu je k ničemu...
Petr Hliněný,   Fl MU Brno, 2011
6/17
Fl: MA010: Vzdálenost v grafech
3.3   Vážená (ohodnocená) vzdálenost
Definice: Vážený graf je graf G spolu s ohodnocením w hran reálnými čísly w : E(G) iž.
Kladně vážený grafG,w je takový, že w(e) > 0 pro všechny hrany e. □
Definice 3.9. (vážená vzdálenost)   Mějme (kladně) vážený graf G, w. Délkou váženého sledu S — (t>o, ei, t>i, e2, V2, ■ ■ ■, en, vn) v G myslíme součet
<Íg(S) — w(ei) + w(e2) H-----h w(e„).
Váženou vzdáleností v G,w mezi dvěma vrcholy u,v pak myslíme
c[q(u, v) — mm{dQ(S) : S je sled s konci u, v} .□
Důležitým faktem je, že stejné definice a dobré vlastnosti zůstávají v platnosti i pro vzdálenost na orientovaných grafech. Obdobně Oddílu 3.1 nyní snadno dokážeme:
Fakt: Nejkratší sled v kladně váženém grafu je vždy cestou (příp. orientovanou). □
Lema 3.10. Vážená vzdálenost v nezáporně vážených grafech (i orientovaných grafech ) splňuje trojúhelníkovou nerovnost.
Petr Hliněný,   Fl MU Brno, 2011
7/17
Fl: MA010: Vzdálenost v grafech
Příklad 3.11. Podívejme se na následující ohodnocený graf (čísla u hran udávají jejich váhy-délky.)
c
Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi b, c. Co ale mezi a, c? i Je jejich vzdálenost 6?   Kdepak, vzdálenost a, b je 5, její cesta vede po „horních" vrcholech. C
Petr Hliněný,   Fl MU Brno, 2011
8/17
Fl: MA010: Vzdálenost v grafech
Záporné délky hran
Doposud jsme důsledně vyžadovali nezápornost (lépe kladnost) ohodnocení délky hran; ale co je na hranách záporné délky tak „špatného"?
x
Takže jaká je v našem grafu vzdálenost mezi x,y? Je to 3 nebo 1? □ Ne, vzdálenost z x do y je —oo.
Stejný problém nastane, kdykoliv je možno opakovat záporné hrany, tedy vždy v neorientovaných grafech a částečně i v orientovaných grafech obsahujících „záporné cykly".
Uvedené příklady problémů se zápornými délkami sledů nás vedou k úplnému vyloučení záporných vah hran v našem výkladu. V jistých omezených případech přesto má smysl hledat nejkratší cesty i v záporných vahách, ale tomu se v našem textu nebudeme věnovat z důvodu nedostatku místa.
Petr Hliněný,   Fl MU Brno, 2011
9/17
Fl: MA010: Vzdálenost v grafech
3.4   Hledání nejkratší cesty
Pro nalezení nejkratší (vážené) cesty mezi dvěma vrcholy kladně váženého grafu se používá tradiční Dijkstrův algoritmus či jeho vhodná vylepšení.
Takové algoritmy se například používají při vyhledávání vlakových spojení. Pravděpodobně se i vy někdy dostanete do situace, kdy budete nejkratší cestu hledat, proto si popsaný algoritmus včetně jeho vylepšení A* zapamatujte.
Poznámka: Dijkstrův algoritmus je sice poněkud složitější než Algoritmus 3.8, ale na druhou stranu je výrazně rychlejší, pokud nás zajímá jen nejkratší vzdálenost z jednoho vrcholu místo všech dvojic vrcholů. □
Dijkstrův algoritmus
• Je variantou procházení grafu (skoro jako do šířky), kdy pro každý nalezený vrchol ještě máme proměnnou udávající vzdálenost - délku nejkratšího sledu (od počátku), kterým jsme se do tohoto vrcholu zatím dostali. □
• Z úschovny nalezených vrcholů vždy vybíráme vrchol s nejmenší vzdáleností (mezi uschovanými vrcholy) - do takového vrcholu se už lépe dostat nemůžeme, protože všechny jiné cesty by byly dle výběru delší. □
• Na konci zpracování tyto proměnné vzdálenosti udávají správně nejkratší vzdálenosti z počátečního vrcholu do ostatních.
Petr Hliněný,   Fl MU Brno, 2011
10/17
Fl: MA010: Vzdálenost v grafech
Algoritmus 3.12. Dijkstrův pro nejkratší cestu v grafu
Tento algoritmus nalezne nejkratší cestu mezi vrcholy u a v kladně váženého grafu G. vstup < graf na N vrcholech daný maticí vzdáleností sousedů del[,] > 0,
kde del [i, j ] =00 pokud j není sousedem i vstup < u, v, kde hledáme cestu z u do v; a
II stav [i] udává zpracovanost vrcholu, vzdal [i] zatím nalezenou vzdálenost
for (i=0; i<N; i++) { vzdal[i] = MAX; stav[i] = inic; }
vzdal[u] = 0;
while (stav[v] ! =zprac.) {
II zde nalezneme nejbližší nezpracovaný vrchol j
m = argmin (vzdal [i]: 0<i<N, stav [i] ==inic.)
if (vzdal [m] ==MAX) return ' Cesta neexistuje' ;
// vrchol m poté zpracujeme, upravíme jeho sousedy
foreach ( k soused m)
if (vzdal [m] +del [m, k] < vzdal [k] ) { prich[k] = m;
vzdal[k] = vzdal[m]+del[m,k];
} _
stav [m] = zprac.; □
}
výstup ' Cesta délky vzdal [v], uložená zpětnými odkazy v poli prich [] ';
Petr Hliněný,   Fl MU Brno, 2011
11/17
Fl: MA010: Vzdálenost v grafech
Poznámka: Uvědomme si, že pokud necháme tento algoritmus proběhnout až do zpracování všech vrcholu, získáme ve vzdal [i] nejkratší vzdálenosti z počátečního vrcholu do všech ostatních vrcholu i.
Všimněme si dále, že Algoritmus 3.12 počítá nejkratší cestu i v orientovaném grafu.
Příklad 3.15. Ukázka běhu Dijkstrova Algoritmu 3.12 pro nalezení nejkratší cesty mezi vrcholy u, v v následujícím grafu.
oo f.
oo M.
oo 1 °c
2    ' x
'       \ 2
3 \
/ \
oc
'■ji oc
2     \   Q   / .      / 1
------k
u
1
oc
Petr Hliněný,   Fl MU Brno, 2011
12/17
Fl: MA010: Vzdálenost v grafech
Fakt: Celkový počet kroků potřebný v Algoritmu 3.12 k nalezení nejkratší cesty z u do v je zhruba N2, kde N je počet vrcholů grafu. □
Na druhou stranu, při lepší implementaci grafu seznamem sousedů a použití vhodné úschovny nezpracovaných vrcholů (implementované haldou s nalezenou vzdáleností jako klíčem) lze dosáhnout i mnohem rychlejšího běhu tohoto algoritmu na řídkých grafech - času téměř úměrného počtu hran grafu, přesněji 0(\E(G)\ + NlogN). □
Věta 3.13. V každé iteraci Algoritmu 3.12 (počínaje stavem po prvním průchodu cyklem while () ) proměnná vzdal [i] udává nejkratší vzdálenost z vrcholu u do vrcholu i při cestě pouze po vnitřních vrcholech x, jejichž stav [x] ==zprac.u
Důkaz: Stručně matematickou indukcí:
• V prvním kroku algoritmu je jako vrchol ke zpracování vybrán první j=u a potom jsou jeho sousedům upraveny vzdálenosti od u podle délek hran z u. □
• V každém dalším kroku je vybrán jako vrchol m ke zpracování ten, který má ze všech nezpracovaných vrcholů nejkratší nalezenou vzdálenost od počátku u. To znamená, že žádná kratší cesta z u do m nevede, neboť každá „oklika" přes jiné nezpracované vrcholy musí být delší dle výběru m a indukčního předpokladu.□
Naopak každá nová nejkratší cesta z u do nezpracovaného vrcholu k procházející přes m musí mít m coby předposlední vrchol, tj. poslední hranu mk, a proto je upravená hodnota vzdal [k] správná i po přidáním mezi zpracované vrcholy.
C
3.5   Pokročilé plánování cest
• Třebaže je Dijkstrův algoritmus velmi rychlý a „téměř optimální" mezi všemi způsoby hledání nejkratší cesty v nezáporně váženém grafu, stále zůstává příliš pomalým pro praktické nasazení třeba v přenosných navigačních zařízeních, jež obsahují mapová data v rozsahu desítek až stovek miliónů hran grafu. □
• Co však může být uděláno lépe?n
• Odpovědí je vhodné předzpracování grafu: Lze dobře očekávat, že samotný graf je relativně stabilní a pro jeho předzpracování je k dispozici dostatek času na výkonných strojích. □
• V tomto místě však vyvstává sekundární problém, kde uložit výsledky předzpracování? Určitě není reálné ukládat (např.) všechny nejkratší cesty mezi všemi dvojicemi vrcholů.. . □
• Dva z nejjednodušších úsporných přístupů k předzpracování grafu pro rychlé plánováni cest si nyní zběžně ukážeme.
Petr Hliněný,   Fl MU Brno, 2011
15/17
Fl: MA010: Vzdálenost v grafech
Lépe než Dijkstrův algoritmus se chová vylepšený algoritmus A", který použitím vhodného potenciálu „směřuje" celé prohledávání grafu ke správnému cíli a je skvěle použitelný ve všech situacích, kdy pojem „směr k cíli" má význam. To je například při navigování v mapě.
Algoritmus A*
• Je reimplementací Dijkstrova algoritmu s „vhodně" upravenými délkami hran.
• Nechť „potenciál" pv(x) udává libovolný dolní odhad vzdálenosti z vrcholu x do cíle v. Například při navigaci v mapě může pv(x) udávat přímou (Euklidovskou) vzdálenost z bodu x do bodu v. □
• Každá (orientovaná!) hrana xy grafu G,w dostane nové délkové ohodnocení w'(xy) — w(xy) + pv(y) — pv(x). Potenciál pv je přípustný, pokud všechna upravená ohodnocení jsou nezáporná, neboli w(xy) >pv(x) —pv(y).
Potenciál přímé vzdál, z x do cíle v je vždy přípustný podle trojúh. nerovnosti. □
• Upravená délka lib. sledu S z u do v pak je cÍq (S) — c[q(S) + pv(v) —pv(u), což je konstantní rozdíl oproti původní délce S. Takže S je optimální pro původní délkové ohodnocení w, právě když je optimální pro nové w'.
Dijkstrův algoritmus pro w' upravené potenciálem přímé vzdálenosti do v pak bude „silně preferovat" hrany vedoucí ve směru k cíli v.
Petr Hliněný,   Fl MU Brno, 2011
16/17
Fl: MA010: Vzdálenost v grafech
Myšlenka „dosahu" (reach)
• Tento přístup těží z přirozeného poznatku, že valná většina hran reálné cestní sítě je pro globální plánování cest vpodstatě „bezvýznamná".□
Definice: Nechť Su,v značí ve váženém grafu G optimální sled z u do v. Nechť dále
pro e G E(SUjV) značí prefix(SUjV, e), suffíx(SUtV,e) celý úsek sledu SUjV před (za) jeho hranou e. uDosah hrany e G E (G) je dán vztahem
reacho(e) — max { min( d,Q(prefíx(SUtV, e)), d,Q(suffíx(SUtV, e))) : V-řt,-y G F (G) A e G E(Su,v)}.n
Dosah hrany e presne matematicky kvantifikuje „(bez)významnost" e pro plánovaní cest; čím menší je reachaífi), tím blíže počátku nebo cíle opt. cesty musí hrana e být. Neboli, prakticky, hrany s malým reacha(e) lze pro většinu dotazu na optimální cesty ignorovat. . . □
Předpočítaného parametru dosahu hran lze přirozeně využít v obousměrné variantě Dijkstrova algoritmu (včetně A*) ke vskutku radikální redukci počtu prohledávaných vrcholů při hledání nejkratší cesty:
• V řádku "foreach (k soused m)" (viz Algoritmus 3.12) prostě akceptujeme pouze ty sousedy k pro které platí reachai^cík) > vzdal [m].
Petr Hliněný,   Fl MU Brno, 2011
17/17
Fl: MA010: Vzdálenost v grafech