3 Vzdálenost a metrika v grafech V minule lekci jsme mluvili o souvislosti grafu, tj. o možnosti procházen í z jednoho vrcholu do jiného. Nekdy je prostá informace o souvislosti dostaCuj íc í, ale vetsinou bychom rádi vedeli i jak je z jednoho vrcholu do druheho daleko . . . b V jednoduss ím prípade se pri zjistovan í grafove vzdalenosti d ívame jen na minimaln í pocet proslych hran z vrcholu do vrcholu. V obecnem prípade vsak pri urcovan í vzdalenosti bereme do uvahy delky jednotlivých hran podel cesty (tyto delky musí byt nezaporne!). c StruCný přehled lekce • Vzdálenost v grafech a její vlastnosti. • VýpoCet metriky grafu (Floyd-Warshall). • DijkstrUv algoritmus pro nejkratsí (ohodnocenou) cestu v grafu. 1 FI: MA010: Vzdálenost v grafech Petr Hliněný, FI MU Brno X c 3.1 Vzdálenost v grafu Vzpomeňme si, že sledem delky n v grafu G rozumíme posloupnost vrcholu a hran v0, ei, vi, e2, v2,..., en, vn, ve ktere hrana &i ma koncove vrcholy Vj. Definice 3.1. Vzdálenost dG(u,v) dvou vrcholu u,v v grafu G je dana delkou nejkratsího sledu mezi u a v v G. Pokud sled mezi u, v neexistuje, je vzdalenost dG(u,v) = to. c Neformálne receno, vzdalenost mezi u, v je rovna nejmenšímu poctu hran, ktere musíme proj ít, pokud se chceme dostat z u do v. Specialne do(u,u) = 0. Uvedomme si, ze nejkratsí sled je vzdy cestou (vrcholy se neopakuj í) - Veta 2.2. Fakt: V neorientovanem grafu je vzdálenost symetrickí, tj. dG(u,v) = dG(v,u). c Lema 3.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: Vu, v,w G V(G) : <Íg(u, v) + cÍg(v,w) > cÍg(u, w). DUkaz. Nerovnost snadno plyne ze zřejmého pozorovaní, ze na sled delky dG(u,v) mezi u, v lze navazat sled delky dG(v, w) mezi v, w, címz vznikne sled delky dG(u, v) + dG(v,w) mezi u,w. Skutecna vzdalenost mezi u,w pak uz muze byt jen mensí. □ Petr Hliněný, FI MU Brno 2 FI: MA010: Vzdálenost v grafech Věta 3.3. Necht 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 ž vrcholu u je vrchol v naležen dříve než vrchol w. □ Důkaz. Postupujeme indukcí podle vzdálenosti do(u,v): Pro do(u,v) = 0, tj. u = v je tvrzení jasne - vrchol u jáko počátek prohledávání byl náležen první. Proto necht do (u, v) = d > 0 á oznáčme v' sousedá vrcholu v bližSího k u, tedy do(u, v') = d — 1. Obdobne uvážme libovolneho sousedá w' vrcholu w. Pák do(u, w') > do(u, w) — 1 > do(u, v) — 1 = do(u, v'), á tudíž vrchol v' byl náležen v prohledávání do sirky dríve než vrchol w' podle indukcního předpokládu. To žnámená, že v' se dostál do fronty uschovny dríve než w'. Proto sousede v' (meži nimá v) jsou při pokrácujícím prohledávání táke náleženi dríve než sousede w' (meži nimá w). □ □ Důslěděk 3.4. Algoritmus prochažení grafu do šižky lže použít pro výpočet grafove vždalenosti ž daného vrcholu u. □ Důsledek 3.4 funguje jen pro "vzdálenost" s jednotkovou délkou vsech hran. My si dále ukážeme obecnější Dijkstrův algoritmus, který obdobným postupem poCítá nejkratsí vzdálenost pri libovolne kladne ohodnoceních delkách hran. Petr Hliněný, FI MU Brno_3_FI: MA010: Vzdálenost v grafech Definice. Mějme graf G. Definujeme (vzhledem k G) následující pojmy a značení: • Excentricita vrcholu exc(v) je nejdelSí vzdálenost z v do jineho vrcholu grafu; exc(v) = maxxev(g) dG(v, x). c • Průměr diam(G) grafu G je nejvetSí excentricita jeho vrcholu, naopak poloměr rad(G) grafu G je nejmenSí excentricita jeho vrcholu. c • Centrem grafu je mnoZina vrcholu U C V (G) takových, jejichZ excentricita je rovna polomeru rad(G). c • Steinerová vzdálenost mezi vrcholy libovolne podmnoZiny W C V(G) je rovna minimálnímu poctu hran souvisleho podgrafu v G obsahujícího vSechny vrcholy W. Petr Hliněný, FI MU Brno_4_FI: MA010: Vzdálenost v grafech 3.2 Výpočet metriky Definice: Metrikou grafu myslíme soubor vzdáleností mezi vsemi dvojicemi vrcholu grafu. Jinak řečeno, metrikou grafu G je matice (dvourozmerne pole) d[,], ve kterem prvek d[i,j] udaví vzdalenost mezi vrcholy i a j. c Metoda 3.5. Dynamický výpočet metriky skládáním cest • Na pocatku nechť d[i,j] udava 1 (prípadne delku hrany {i, j}), nebo oo pokud hrana mezi i, j není. c • Po kazdem kroku t > 0 necht d[i,j] udava delku nejkratsí cesty mezi i, j, ktera jde pouze pres vnitrní vrcholy z mnoziny {0,1, 2,..., t — 1}. c • Při prechodu z t na nasledující krok t +1 upravujeme vzdalenost pro kazdou dvojici vrcholu - jsou vzdy pouhe dve moznosti: - Bud' je cesta delky d[i,j] z předchozího kroku stale nejlepsí (tj. nove povoleny vrchol t nam nepomuze), - nebo cestu vylepsíme spojením pres nove povoleny vrchol t, címz získame mensí vzdalenost d[i,t]+d[t,j]. Veta 3.6. Metoda 3.5 v poli d[i,j] správně vypočte vzdálenost mezi vrcholy i, j. Petr Hliněný, FI MU Brno 5 FI: MA010: Vzdálenost v grafech 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 sousednosti G[] [] grafu na N vrcholech (číslovaných 0. . .N-1), kde G[i,j]=1 pro hranu mezi i, j a G[i,j]=0 jinak; for (i=0; i 0 pro vSechny hrany e. c Definice: Mejme (kladne) važený graf G, w. Delkou važeneho sledu S = vo, ei,vi,-e2, v2,..., en, vn v G myslíme součet dG(S) = w(ei) + w(e2) H-----h w(e„) . Váženou vzdálenosti v G, w meži dvema vrcholy u, v pak myslíme dG(u, v) = min{dG(S) : S je sled s konci u, v} .c Obdobne Oddílu 3.1 snadno dokažeme: Lemá 3.9. Vážená vzdálenost v kladne vážených grafech také splěuje trojúhelníkovou nerovnost. Petr Hliněný, FI MU Brno FI: MA010: Vzdálenost v grafech Vzdálenost mezi vrcholy a,c je 3, stejně tak mezi b,c. Co ale mezi a, c? aJe jejich vzdálenost 6? nKdepak, vzdálenost a, b je 5, cesta vede po „horních" vrcholech. A jaka je v nasem druhem grafu vzdalenost mezi x,y? Je to 3 nebo 1? c Ne, ta vzdalenost je —oo. To je nakonec dobry dUvod, proč zakazat zaporne hrany. Petr Hliněný, FI MU Brno FI: MA010: Vzdálenost v grafech c x 3.4 Hledání nejkratší cesty Pro nalezen í nejkratší (vážené) cesty mezi dvema vrcholy kladně váženého grafu se použ íva tradicn í Dijkstrův algoritmus Ci jeho vhodna vylepšen í. Takove algoritmy se napríklad používaj í při vyhledavan í vlakových spojen í. Pravdepodobne se i vy nekdy dostanete do situace, kdy budete nejkratsí cestu hledat, proto si popsany algoritmus vcetne jeho vylepsen í A* zapamatujte. Poznámka: Dijkstrův algoritmus je sice poněkud složitější nez Algoritmus 3.7, ale na druhou stranu je výrazně rychlejší, pokud nás zajímá jen nejkratsí vzdálenost z jednoho vrcholu místo vsech dvojic vrcholu. c Dijkstrův algoritmus • Je variantou prochazen í grafu (skoro jako do sířky), kdy pro každy nalezeny vrchol jeste mame proměnnou udávající vzdálenost - delku nejkrats ího sledu (od pocatku), kterym jsme se do tohoto vrcholu zat ím dostali. c • Z uschovny nalezenych vrcholu vždy vyb írame vrchol s nejmensí vzdaleností (mezi uschovanymi vrcholy) - do takoveho vrcholu se už lepe dostat nemužeme, protože vsechny jine cesty by byly dle vyberu delsí. c • Na konci zpracovan í tyto promenne vzdalenosti udavaj í spravne nejkratsí vzdalenosti z pocatecn ího vrcholu do ostatn ích. Petr Hliněný, FI MU Brno_9_FI: MA010: 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 dany seznamem sousedU sous [] [] a del [] [], kde sous [i] [0] sous [i] [st [i] -1] jsou sousede vrcholu i stupne st [i] a hrana z i do sous [i] [k] ma delku del [i] [k] >0; input: u,v, kde hledáme cestu z u do v; c // stav [i] udava zpracovanost vrcholu, vzdal [i] zatím nalezenou vzdalenost for (i=0; i<=N; i++) { vzdal[i] = MAX.INT; stav[i] = 0; } vzdal[u] = 0;c while (stav[v]==0) { for (i=0, j=N; i oc ""■ji oc 2 s 0 7 s 0 / oc 1 1 Petr Hliněný, FI MU Brr FI: MA010: Vzdálenost v grafech Fákt: Celkovy pocet kroku potrebny v Algoritmu 3.10 k naležení nejkratsí cesty ž u do v je žhruba N2, kde N je pocet vrcholu grafu. c Na druhou stranu, pri lepsí implementaci uschovny nežpracovanych vrcholu (třeba haldou s naleženou vždaleností jako klícem) lže dosahnout i mnohem rychlejsího behu tohoto algoritmu na řídkych grafech - casu temeř umerneho poctu hran grafu. c Vetá 3.12. V každe iteraci Algoritmu 3.10 (počínaje stavem po prvním pmchodu cýk-lem while () ) proměnná vzdal [i] udáva nejkratsívždálenost ž vrcholu u do vrcholu i pěi ceste použe po vnitěních vrcholech x, jejichž stav[x]==1. c Důkáz: Strucne matematickou indukcí: • V prvním kroku algoritmu je jako vrchol ke žpracovaní vybran první j=u a potom jsou jeho sousedum upraveny vždalenosti od u podle delek hran ž u. c • V každem dalsím kroku je vybran jako vrchol j ke žpracovaní ten, ktery ma že vsech nežpracovanych vrcholu nejkratsí naleženou vždalenost od pocatku u. To ale žnamena, že žadna kratsí cesta ž u do j nevede, nebot každa „oklika" přes jine nežpracovane vrcholy musí byt delsí dle vyberu j a indukcního predpokladu. (V tomto bode potřebujeme nežapornost ohodnocení del [] [].) c Naopak kařžda nova nejkratřs í cesta ž u do nežpracovaneho vrcholu i prochažej íc í přes j musí mít j coby predposlední vrchol, tj. poslední hranu ij, a proto je upravena hodnota vzdal[i] spravna i po přridan í j meži žpracovane vrcholy. □ V Petr Hliněný, FI MU Brr FI: MA010: Vzdálenost v grafech Jeste lepe nez Dijkstmv algoritmus se chova vylepseny algoritmus A*, ktery pouzitím vhodneho potencialu „smeruje" cele prohledavan í grafu ke spravnemu cíli a je skvele pouzitelny ve vsech situac ích, kdy pojem „smer k c íli" ma vyznam. To je napríklad pri navigovan í v mape. Algoritmus A* • Je reimplementac í Dijkstrova algoritmu s „vhodně" upravenými delkami hran. c • Nechť „potencial" pv(x) udava libovolny doln í odhad vzdalenosti z vrcholu x do c íle v. Například při navigaci v mape muzepv(x) udavat prímou (Euklidovskou) vzdalenost z bodu x do bodu v. c • Kazda (orientovana!) hrana xy grafu G, w dostane nove delkove ohodnocen í w'(xy) = w(xy) + pv(y) — pv(x). Potencial pv je přípustný, pokud vsechna upravena ohodnocen í jsou nezaporna, neboli w(xy) > pv(x) — pv (y). Potencial príme vzdal. z x do c íle v je vzdy přípustny podle trojuh. nerovnosti. • Upravena delka lib. sledu S z u do v pak je dG (S) = + pv(v) — pv(u), coz je konstantn í rozd íl oproti puvodn í delce S. Takze S je optimaln í pro puvodn í delkove ohodnocen í w, prave kdyz je optimaln í pro nove w'. Dijkstmv algoritmus pro w' upravene potencialnem příme vzdalenosti do v pak bude „silne preferovat" hrany vedouc í ve smeru k c íli v. V Petr Hliněný, FI MU Brr FI: MA010: Vzdalenost v grafech