3 Vzdálenost a metrika v grafech V minulé lekci jsme mluvili o souvislosti grafu, tj. o možnosti procházení z jednoho vrcholu do jiného. Někdy je 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. • Výpočet metriky grafu (Floyd-Warshall). • Dijkstrův algoritmus pro nejkratší (ohodnocenou) cestu v grafu. ________;tr Hliněný, Fl MU Brn< IA010: Vzdálenost v grafech Vzpomeňme si, že sledem délky n v grafu G rozumíme posloupnost vrcholů a hran vo, ei, vi, ei-, V2, • • •, en, vn, ve které hrana ej má koncové vrcholy Vj_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 u,v neexistuje, je vzdálenost do(u,v) = oo. c Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme projít, pokud se chceme dostat z u do v. 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. do(u,v) = do(v,u). c Lema 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: Vu,v,wGV(G) : do(u,v) + do(v,w) > do(u,w). Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky do(u,v) mezi u, v lze navázat sled délky do(v, w) mezi v, w, čímž vznikne sled délky do(u, v) + do(v,w) mezi u,w. Skutečná vzdálenost mezi u,w pak už může být jen menší. D Petr Hliněný, Fl MU Brno 2 Fl: MA010: Vzdálenost v grafech Věta 3.3. Nechť u,v,w jsou vrcholy souvislého grafu G takové, že do(u,v) < do(u, w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w. a Důkaz. Postupujeme indukcí podle vzdálenosti da(u,v): Pro da(u,v) = 0, tj. u = v je tvrzení jasné - vrchol u jako počátek prohledávání byl nalezen první. Proto nechť da(u, v) = d > 0 a označme v' souseda vrcholu v bližšího k u, tedy da(u,v') = d— 1. Obdobně uvažme libovolného souseda w' vrcholu w. Pak da(u, w') > da(u, w) — í > da(u, v) — í = da(u, v'). 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 nima v) jsou při pokračujícím prohledávání také nalezeni dříve než sousedé w' (mezi nima w). U 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. c Důsledek 3.4 funguje jen pro "vzdálenost" 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. _________tr Hliněný, Fl MU Brn A010: Vzdálenost v grafech ^ Další pojmy a fakta Definice. Mějme graf G. Definujeme (vzhledem k G) následující pojmy a značení: • Excentricita vrcholu exc(v) je nejdelší vzdálenost z» do jiného vrcholu grafu; exc(w) = maxiey(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ů, d • Centrem grafu je množina vrcholů U C V (G) takových, jejichž excentricita je rovna poloměru rad(G). d • Steinerova 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. I: MA010: Vzdálenost v grafech y --- _ 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. o Metoda 3.5. Dynamický výpočet metriky skládáním cest • Na počátku nechť d[i, j] udává 1 (případně délku hrany {i,j}), nebo oo pokud hrana mezi i, j není. • Po každém kroku ŕ > 0 nechť d[i, j] udává délku nejkratší cesty mezi i,j, která jde pouze přes vnitřní vrcholy z množiny {0,1, 2,... ,t — 1}. • Při přechodu z t na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů -jsou vždy pouhé dvě možnosti: — Buď je cesta délky d [i, j] z předchozího kroku stále nejlepší (tj. nově povolený vrchol t nám nepomůže), — nebo cestu vylepšíme spojením přes nově povolený vrchol t, čímž získáme menší vzdálenost d[i,t]+d[t, j]. Věta 3.6. Metoda 3.5 v poli d [i, j ] správně vypočte vzdálenost mezi vrcholy i, j. N^. Petr Hliněný, Fl MU Brno I: MA010: Vzdálenost v grafech r Poznámka: V implementaci pro symbol oo použijeme velkou konstantu, třeba MAX_INT/2. Algoritmus 3.7. Výpočet metriky grafu; Floyd-Warshall input: matice soused'nosti G [] [] 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 R. Kladně vážený grafG, w je takový, že w(e) > 0 pro všechny hrany e. Definice: Mějme (kladně) vážený graf G,w. Délkou váženého sledu S = «o, ei,«!,-ď2, V2, ■ ■ ■, en, vn v G myslíme součet d?Ci(S) = w(e1) + w(e2) + • • • + w(en) . Váženou vzdáleností v G,w mezi dvěma vrcholy u,v pak myslíme cIq(u, v) = min{dQ(S) : S je sled s konci u, v} .c Obdobně Oddílu 3.1 snadno dokážeme: Lema 3.9. Vážená vzdálenost v kladně vážených grafech také splňuje trojúhelníkovou nerovnost. Petr Hliněný, Fl MU Brno 7 Fl: MA010: Vzdálenost v grafech Vzdálenost mezi vrcholy a, c je 3, stejně tak mezi b,c. Co ale mezi a,c? Je jejich vzdálenost 6? Kdepak, vzdálenost a, 6 je 5, cesta vede po „horních" vrcholech. A jaká je v našem druhém grafu vzdálenost mezi x,yl Je to 3 nebo 1? c Ne, ta vzdálenost je — oo. To je nakonec dobrý důvod, proč zakázat záporné hrany. Detr Hliněný, Fl MU Bn 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.7, 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ů, c 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, c • 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ší, d • 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. ________tr Hliněný, Fl MU Brn : Vzdálenost v grafech ^ Algoritmus 3.10. Dijkstrův pro nejkratší cestu v grafu Tento algoritmus nalezne nejkratší cestu mezi vrcholy u a v kladně váženého grafu G. input: graf na N vrcholech daný seznamem sousedů sous [] [] a del [] [], kde sous [i] [0] , . . . , sous [i] [st [i] -1] jsou sousedé vrcholu i stupně st [i] a hrana z i do sous [i] [k] má délku del [i] [k] >0; input: u,v, kde hledáme cestu zu do v;c // stav [i] udává zpracovanost vrcholu, vzdal [i] zatím nalezenou vzdálenost for (i=0; i<=N; i++) { vzdal[i] = MAX.INT; stav[i] = 0; } vzdal[u] = 0;d while (stav[v]==0) { for (i=0, j=N; i oc ~yi oc >etr Hlinený, Fl MU Bri : MAOIO: Vzdálenost v grafech 3etr Hliněný, Fl M 2 Nffi fef 2 D U ! Fl: MAOIO: Vzdálenost v grafech Fakt: Celkový počet kroků potřebný v Algoritmu 3.10 k nalezení nejkratší cesty z u do z v je zhruba N , kde N je počet vrcholů grafu. Na druhou stranu, při lepší implementaci úschovny nezpracovaných vrcholů (třeba 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, a Věta 3.12. V každé iteraci Algoritmu 3.10 (počínaje stavem po prvním průchodu cyklem while OJ 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] ==1. c 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 j ke zpracování ten, který má ze všech nezpracovaných vrcholů nejkratší nalezenou vzdálenost od počátku u. To ale znamená, že žádná kratší cesta z u do j nevede, neboť každá „oklika" přes jiné nezpracované vrcholy musí být delší dle výběru j a indukčního předpokladu. (V tomto bodě potřebujeme nezápornost ohodnocení del [] [].) Naopak každá nová nejkratší cesta z u do nezpracovaného vrcholu i procházející přes j musí mít j coby předposlední vrchol, tj. poslední hranu i j, a proto je upravená hodnota vzdal [i] správná i po přidání j mezi zpracované vrcholy. Petr Hliněný, Fl MU Brno 13 Fl: MA010: Vzdálenost v grafech Ještě 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-y. Například při navigaci v mapě můžepv(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é vzdal, z x do cíle v je vždy přípustný podle trojúh. nerovnosti. • Upravená délka lib. sledu Sztidoti pak je ď£ (S) = /