P B165 - Grafy a sítě Hledání nejkratších cest □ S Obsah přednášky O Úvod Q Nejkratší cesty z jednoho vrcholu 9 Dijkstrův algoritmus • A* algoritmus • Bellman-Ford algoritmus Q Cesty mezi všemi vrcholy • Floyd-Warshallův algoritmus • Distribuovaný Floyd-Warshallův algoritmus □ s Vzdálenost v grafu Pro připomenutí: • Délka cesty v neohodnoceném grafu je rovna počtu hran na této cestě. • Vzdálenost ö(u, v) vrcholů u, v v grafu je délka nejkratší cesty z u do v. • Vzdálenost mezi dvěma vrcholy nemusí být v případě orientovaného grafu symetrická. Obrázek: Nejkratší cesty z u do v a naopak se liší. Vzdálenost v ohodnoceném grafu V reálných aplikacích hledání nejkratších cest jsou hrany grafu obvykle nějakým způsobem ohodnoceny - např. vzdálenosti mezi městy silniční sítě, latence síťových spojů. Definice Délka cesty v ohodnoceném grafu je rovna součtu ohodnocení hran na této cestě. • Vzdálenost vrcholů je opět rovna délce nejkratší cesty. • Aby měl pojem vzdálenosti význam, v grafu nemůže existovat cyklus záporné délky. Nechť je součástí sledu s cyklus c. Tento cyklus má zřejmě kladnou délku. Potom existuje sled, který je "podsledem" s a cyklus c je z něj "vystřižen". Jelikož c má kladnou délku, je tento sled kratší než sled c obsahující. Takto lze pokračovat a sled zkracovat, dokud obsahuje nějaké cykly. Výsledný sled, který neobsahuje žádný cyklus, je cestou. D Obrázek: Nejkratší sled je vyznačen červeně. Delší sledy vedou i po modrých a zelených hranách a tvoří cykly. Graf G splňuje trojúhelníkovou nerovnost, pokud pro libovolnou trojici jeho vrcholů u, v, w platí: ö(u, w) < ö(u, v) + ö(v, w) d(u,w) Obecný graf tuto nerovnost nesplňuje. Příkladem, pro který trojúhelníková nerovnost platí, je např. graf nejkratších silničních vzdáleností mezi městy. _ooooooooooooooo Dijkstrův algoritmus • "Klasický" algoritmus hledání nejkratší cesty. • Najde nejkratší cesty z jednoho vrcholu do všech ostatních. • Musí proto projít všechny vrcholy. • Pracuje pro orientovaný i neorientovaný graf. • Vyjma nezáporných cyklů vyžaduje nezáporné ohodnocení všech hran. • Lineární paměťová složitost. • Časová složitost záleží na použité datové struktuře. • Počáteční vrchol označíme s. • Pro každý vrchol v grafu je udržována hodnota d [v] - délka nejkratší nalezené cesty z s do v. • Na počátku d[s]= 0 pro počáteční vrchol a d[v]= oo pro ostatní vrcholy. • Po skončení výpočtu obsahuje d [v] délku nejkratší cesty v grafu, pokud taková existuje, nebo oo v opačném prípade. • Dále v proměnné p [v] ukládáme předchůdce vrcholu v na doposud nalezené nejkratší cestě z u. • Před výpočtem nastavíme hodnotu p [v] jako nedefinovanou pro všechny vrcholy. • Po skončení výpočtu je nejkratší cesta posloupnost vrcholu s, p [. . . p [v] . . . ] , ... p [p [v] ] , p [v] , v. n 3 - = -E -00*0 • Všechny vrcholy jsou rozděleny do dvou vzájemně disjunktních množin: • S obsahuje všechny vrcholy, pro něž je v d [v] uložena definitivní nejkratší cesta z s do v v grafu. • Q obsahuje všechny ostatní vrcholy. • Vrcholy množiny Q jsou ukládány v prioritní frontě. • Nejvyšší prioritu má vrchol u s nejnižší hodnotou d[u] - nelze do něj již nalézt kratší cestu než která je aktuální. • V každé iteraci jsou provedeny následující kroky: • Odstraň vrchol u z počátku fronty. • Přesuň vrchol u z množiny Q do S. • Relaxuj všechny hrany (u, v): • Pokud d[v] > d[u] +w(u, v), uprav d[v]. • w(u, v) značíme ohodnocení (weight) hrany (u, v). □ g - = ^ -00*0 Vycházíme z počátečního vrcholu s, nek. značíme oo. Vlož všechny vrcholy do Q. d[s] = 0; p[s] = nedef; Pro všechny vrcholy v grafu vyjma počátečního: I d[u] = nek. I p[u] = nedef. Dokud není Q prázdna: I Odstraň z Q vrchol u s nejvyšší prioritou I Pro všechny hrany (u, v) proveď : I | Pokud d [v] > d[u] + w(u,v) I I I d[v] = d[u] + w(u,v) I I I p [v] = u Dijkstrův algoritmus - příklad Obrázek: Vrcholy množiny S jsou vyznačeny modře. Napravo od grafu je znázorněn stav prioritní fronty. n S - = -E -00*0 Dijkstrův algoritmus - animace/ilustrace výpočtu • animace výpočtu na ukázkovém grafu • http://www.unf.edu/~wkloster/foundations/ DijkstraApplet/DijkstraApplet.htm • komentovaný výpočet • http://www.youtube.com/watch?v=8LslRqHC0Pw • výpočet s možností definice vlastního grafu • http: //www.cse.yorku.ca/~aaw/HFHuang/DijkstraStart.html • ilustrace výpočtu • http://www.animal.ahrgr.de/showAnimationDetails. php3?lang=en&anim=16 Označme n = \V\,m = \E\. • Inicializace je provedena v lineárním čase vzhledem k počtu vrcholu. • Každou hranou prochází algoritmus vždy právě jednou nebo dvakrát (v prípade neorientovaného grafu). • Hlavní cyklus je proveden vždy nkrát. • Je tudíž provedeno vždy právě n výběrů z prioritní fronty. • Složitost výběru z fronty záleží na její implementaci: • Pole, seznam vrcholů - výběr lze provést v lineárním čase, složitost celého algoritmu je tedy 0(n2 + m). • Binární halda - výběr je proveden v čase ö(log(n)). Při každé relaxaci hrany může dojít k aktualizaci haldy {ö{hg{n)), celková složitost je tak rovna 0((n+ m)log(n)). • Fibonacciho halda - složitost výběru stejná jako v případě binární haldy, složitost úpravy haldy při relaxaci je ovšem konstantní - výsledná složitost algoritmu 0(m + nlog(n)). http://en.wikipedia.org/wiki/Fibonacci_heap □ g - = ^ -00*0 Dijkstrův algoritmus je používán v link-state směrovacích protokolech. Ty pracují na principu zasílání sousedních "vrcholů" aktivními síťovými prvky, které se směrování zúčastní. • Každý aktivní prvek periodicky rozesílá seznam sousedních vrcholů. • Ten je propagován skrze síť ke všem aktivním prvkům. • Každý aktivní prvek nezávisle na ostatních vypočítá strom nejkratších cest do všech ostatních aktivních prvků. • Riziko vzniků smyček v routovacích tabulkách. Nejpoužívanější link-state protokoly jsou OSPF a IS-IS. Oba používají Dijkstrův algoritmus. • Upravený Dijkstrův algoritmus. • Používá se zejména k nalezení cesty do jednoho vrcholu -např. navigace. • Krom délky nejkratší cesty do každého vrcholu bere při vyhledávání v úvahu i heuristický odhad jeho vzdálenosti od cíle. • Každé cestě je přiřazen heuristický odhad délky jako součet ohodnocení jejích hran a heuristické ohodnocení koncového vrcholu. • Do prioritní fronty nejsou ukládány vrcholy grafu, ale cesty. • Nejvyšší prioritu má cesta s nejnižším heuristickým ohodnocením. • Pro každý vrchol je uloženo, je-li již "uzavřen" či nikoliv, tzn., byl-li již navštíven, prozkoumán odebráním z fronty některé cesty v tomto vrcholu končící. Dijkstrův algoritmus lze použít také k nalezení cesty do jednoho vrcholu grafu. Obvykle ale projde mnoho neperspektivních vrcholů - např. při vyhledávání trasy v mapě jde i opačným směrem stejně daleko, jak správným. A* tyto vrcholy eliminuje pomocí heuristiky, je-li vhodně zvolena. • Časová složitost záleží na kvalitě zvolené heuristiky - nejhůře může být exponenciální, nejlépe polynomiální, a to vůči délce optimální cesty. • Paměťová složitost může být v nejhorším případě také exponenciální- existuje několik zlepšujících variant algoritmu. Více informací v přednášce doc. Hliněného: http://www.video.muni.cz/public/ITI/IJI2 ^ivi _ Označme počáteční vrchol s, koncový c. Označ všechny vrcholy jako neuzavřené. Inicializuj prioritní frontu Q vrcholem (cestou) s. Dokud Q není prázdna: I Odstraň cestu p z Q. I Necht' x je koncový vrchol p. I Pokud x je uzavřený: I | pokračuj další iterací. I Pokud x = c: I I Vrať cestu p jako výsledek. I Uzavři x. I Pro všechny hrany (x, y): I | Vlož do fronty cestu p + (x, y) Vrať zprávu o neexistenci cesty. □ g - = ^ -00*0 • Stejně jako Dijkstrův algoritmus vypočítá vzdálenosti všech vrcholů grafu z jednoho zdroje. • Základní strukturou podobný Dijkstrovu algoritmu. • Graf smí obsahovat i záporně ohodnocené hrany. • Cykly s celkovým záporným ohodnocením jsou algoritmem detekovány. • Namísto výběru hrany k relaxaci v každé iteraci relaxuje všechny hrany. • Vyšší časová složitost než Dijkstrův algoritmus - o{mrí). Proměnné d [v] a p [v] mají stejný význam jako u Dijkstrova algoritmu. Počet vrcholů grafu označme n. d[s] = 0; p[s] = undef; Pro všechny vrcholy v grafu vyjma počátečního: I d[u] = nek. I p[u] = nedef. Opakuj n-krát: I Pro všechny hrany (u,v): I | Pokud d [v] > d[u] + w(u,v) I I I d [v] = d[u] + w(u,v) I I I p [v] = u Pro všechny hrany (u,v) opakuj: I Pokud d[v] > d[u] + w(u,v): I | Chyba: graf obsahuje cyklus neg. váhy Bellman-Ford - príklad Obrázek: Relaxované hrany v každém kroku jsou vyznačeny modře. Napravo od grafu je vypsána délka nejkratších cest do vrcholů. V poslední (nezobrazené) iteraci již nedojde k žádným změnám. □ s Bellman-Ford - animace/ilustrace výpočtu komentovaná animace výpočtu (česky) • http://www.youtube.com/watch?v=LrYL6akqpHU komentovaná animace výpočtu (anglicky) • http://www.csanimated.com/animation.php?t= Bellman-Ford_algorithm □ s a Bellman-Ford algoritmus je používán v druhé třídě směrovacích protokolů - distance-vector. • Namísto struktury celého grafu jsou mezi aktivními prvky přenášeny jim známé vzdálenosti do ostatních aktivních prvků. • Každý aktivní prvek periodicky rozesílá tyto sobě známé vzdálenosti k ostatním. • Obdrží-li aktivní prvek tabulku vzdáleností, provede relaxaci hran, případně aktualizuje svoji směrovací tabulku a rozešle svým sousedům. • Distance-vector protokoly mají nižší výpočetní složitost než link-state protokoly. • Nejznámějšími distance-vector protokoly jsou RIP, BGP, EGP. Floyd-Warshallův algoritmus • Vypočítává nejkratší vzdálenost mezi všemi dvojicemi vrcholů v grafu. • Graf může obsahovat záporně ohodnocené hrany, cykly s celkovým záporným ohodnocením vedou k chybnému řešení. a Mezi každými dvěma dvojicemi vrcholů postupně vylepšuje nejkratší známou vzdálenost. • V každém kroku algoritmu je definována množina vrcholů, kterými je možno nejkratší cesty vést. • Každou iterací je do této množiny přidán jeden vrchol. • V každé z n iterací jsou aktualizovány cesty mezi všemi n2 dvojicemi vrcholů. Časová složitost algoritmu je tedy ö(n3). • Paměťová složitost algoritmu je 0(n2). • Nechť jsou vrcholy grafu očíslovány 1... n. • Nejprve algoritmus uvažuje pouze hrany grafu. Následně prohledává cesty procházející pouze vrcholem 1. Poté cesty procházející pouze vrcholy 1, 2, atd. • Mezi každými dvěma vrcholy u, v je v k + 1. iteraci algoritmu známa cesta využívající vrcholů 1... k. • Pro nejkratší cestu mezi těmito vrcholy využívající vrcholů 1... k + 1 jsou dvě možnosti: • Vede opět pouze po vrcholech 1... k. • Vede po vrcholech 1... k z u do vrcholu k + 1 a z něj poté do v. • Na konci výpočtu jsou známy nejkratší cesty využívající všech vrcholů grafu. Floyd-Warshallův algoritmus - pseudokod • V matici d na pozici d [i] [j] je uložena vypočtená vzdálenost vrcholů /,_/'. • Vstupem je graf v podobě matice sousednosti, kde jednotlivé prvky značí ohodnocení hrany nebo oo Pro všechna k od 1 do n: I Pro všechna i od 1 do n: I | Pro všechna j od 1 do n: I | | d[i][j] = minimum(d[i] [j], d[i] [k] d[k][j]) Floyd-Warshallův algoritmus - příklad Obrázek: Vrcholy, kterými mohou vést cesty, jsou vyznačeny. Matice udává nejkratší nalezené vzdálenosti mezi dvojicemi vrcholů. 12 3 4 5 1 018 4 12 ? 2 18 0 ? 5 ? 3 4 7 0 7 3 4 12 5 7 0 2 5 7 7 3 2 0 12 3 4 5 1 0 18 412 7 2 18 0 22 5 7 3 4 22 0 7 3 4 12 5 7 0 2 5 7 7 3 2 0 12 3 4 5 1 0 18 412 7 2 18 0 22 5 7 3 4 22 0 7 3 4 12 5 7 0 2 5 7 7 3 2 0 12 3 4 5 1 0 18 4 11 7 2 18 0 22 5 25 3 4 22 0 7 3 4 11 5 7 0 2 5 7 25 3 2 0 12 3 4 1 0 16 411 2 16 0 12 5 3 412 0 7 4 11 5 7 0 5 7 7 3 2 12 3 0 14 4 2 14 0 10 3 410 0 9 5 5 7 7 3 □ S oooooooooooooooo Distribuovaný Floyd-Warshall Výhodou Floyd-Warshallova algoritmu je jeho snadná aplikace v distribuovaném prostředí- mezi autonomními jednotkami, které si mohou informace předávat jen pomocí zasílání zpráv po síti. • Každý vrchol grafu vypočítává nejkratší cesty do všech ostatních vrcholů grafu. • Na začátku zná každý vrchol jen cestu do svých sousedů. • Stejně jako v sekvenční variantě algoritmu, každá iterace algoritmu přidává jeden vrchol, kterým mohou procházet hledané nejkratší cesty. • Přidaný vrchol v každé iteraci rozešle svoji tabulku vzdáleností ostatním vrcholům grafu. • Ostatní vrcholy pomocí své a přijaté tabulky aktualizují nejkratší cesty do všech vrcholů. Distribuovaný Floyd-Warshall - pseudokód Algoritmus je spuštěn ve vrcholu u. d [u] = 0; p [u] = nedef . Pro všechny ostatní vrcholy v: I Je-li v sousední vrchol: I I d[v] = w(u,v); p[v] = v; I Jinak: I | d[v] = nekon.; p [v] = nedef; Dokud nebyly vybrány všechny vrcholy: I Vyber doposud nevybraný vrchol v. I Pokud u = v: I | Rozešli ostatním vrcholům pole d. I Jinak: I | Přijmi od vrcholu v jeho pole d. I Pro všechny vrcholy w: I | d[w] = minimum (d [w] , d[v]+dv[w]), uprav p [v]. □ s - - • Pro správnost algoritmu je nutné, aby všechny výpočetní uzly (vrcholy grafu) vybraly vždy stejný vrchol, který poté rozesílá svoji tabulku vzdáleností. • Algoritmus je neefektivní z hlediska množství zasílaných dat. Pokud v některém vrcholu platí d[v]= oo pro právě vybraný vrchol v, jeho cesty se nijak neupraví a nemusí mu tedy být zasílána tabulka vzdáleností tohoto vrcholu. • Před rozesláním tabulky vzdáleností se mohou vrcholy vzájemně informovat, které mají obdržet tuto tabulku s výrazně nižšími nároky na přenesená data <= Touegův algoritmus. • Další informace: • Ajay D. Kshemkalyani, Mukesh Singhal. Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, 2008. Str. 151-155 Cvičení O Na grafu níže vypočítejte nejkratší cesty použitím Dijkstrova, Bellman-Fordova a Floyd-Warshallova algoritmu. V prípade prvních dvou použijte různé počáteční vrcholy. Navrhněte způsob implementace nastíněného vylepšení distribuovaného Floyd-Warshallova algoritmu. Uvažujte, že výpočetní uzly mohou zasílat zprávy jen po hranách grafu (broadcasting je implementován přeposíláním zpráv mezi uzly). O Proč nepracuje Dijkstrův algoritmus korektně na grafech obsahujících záporně ohodnocené hrany? K jakým výsledkům může dojít, je-li na takovém grafu spuštěn? O Dokažte tvrzení, označované také jako trojúhelníková nerovnost v grafech: Vu, v, w G V(G) : ö(u, w) < ö(u, v) + ö(v, w) Nechť vstupem Bellman-Fordova algoritmu je graf, v němž každá nejkratší cesta obsahuje nejvýše k hran. Navrhněte úpravu algoritmu umožňující ukončit výpočet po k + 1 iteracích.