Johnsonův algoritmus je algoritmus sloužící k hledání nejkratších cest mezi všemi uzly v ohodnoceném orientovaném grafu, který může mít záporně ohodnocené hrany. V řídkých grafech je rychlejší, než Floydův–Warshallův algoritmus. Johnsonův algoritmus dokáže rozpoznat záporný cyklus v grafu a výpočet ukončit. K tomu využívá Bellmanův-Fordův algoritmus, s jehož pomocí přehodnotí hrany tak, aby žádná neobsahovala zápornou hodnotu. Po přehodnocení hran používá Dijkstrův algoritmus k nalezení nejkratších cest mezi všemi uzly.
Johnsonův algoritmus je pojmenován po Donaldu B. Johnsonovi.
Popis algoritmu Mějme orientovaný graf . Ohodnocení hran označíme jako . Graf může obsahovat záporně ohodnocené hrany.
Johnsonův algoritmus pracuje v několika fázích:
Ke grafu se přidá nový uzel Q, který se propojí se všemi ostatními uzly hranou s nulovým ohodnocením (s nulovou délkou) orientovanou od uzlu Q. Vypočítá se pomocí Bellmanova-Fordova algoritmu nejkratší vzdálenost všech uzlů u ∈ U od pomocného uzlu Q. Tuto vzdálenost označme h(u). Pokud Bellmanův-Fordův algoritmus detekuje záporný cyklus v grafu, dojde k ukončení Johnsonova algoritmu Přehodnotí se ohodnocení hran w(h) tak, aby nové ohodnocení neobsahovalo záporné hodnoty. Přehodnocení hran zachovává nejkratší cesty mezi všemi dvojicemi uzlů. (Hrana h je hrana z uzlu ui do uzlu uj.)
Odstraní se uzel Q. Pomocí Dijkstrova algoritmu nad přehodnoceným grafem se vypočítají vzdálenosti mezi všemi uzly. Aplikuje se tedy Dijkstrův algoritmus na všechny uzly u ∈ U. Pro výpočet původních vzdáleností v grafu lze aplikovat zpětnou transformaci na -vzdálenosti vygenerované Dijkstrovým algoritmem. (Zpětná transformace funguje i na cesty z ui do uj.)
Příklad vpravo|Příklad Johnsonova algoritmu - inicializace.Řídký graf o 5 uzlech a 6 hranách, z toho 2 hrany jsou záporně ohodnocené. Graf neobsahuje záporný cyklus.
Ke grafu byl přidán pomocný uzel Q a připojen ke všem uzlům grafu hranou s hodnotou 0 orientovanou od uzlu Q.vpravo|Příklad Johnsonova algoritmu - Bellmanův-Fordův algoritmus hledání nejkratších cest z uzlu Q.u ABCDEh(u) 0 -2 -3 -1 0 Pomocí Bellmanova-Fordova algoritmu se vypočítala vzdálenost h(u) všech uzlů grafu od Q.
Žádná ze vzdáleností h(u) není kladná. To proto, že z uzlu Q vede do každého uzlu grafu přímo hrana s ohodnocením 0. Kratší cesta pak může být jedině záporná.vpravo|Příklad Johnsonova algoritmu - přehodnocení hran.h A→BB→CB→EC→DD→AE→C -2 4 3 2 2 -3 0 5 1 0 1 0 Hrany grafu byly přehodnoceny podle vztahu:
.
Nyní jsou všechny nezáporně ohodnocené, přičemž mezi každými dvěma uzly jsou zachovány nejkratší cesty.
Na obrázku je nové ohodnocení hran uvedeno v závorkách.vpravo|Příklad Johnsonova algoritmu - Dijkstrův algoritmus, hledání nejkratších cest z uzlu A.Na závěr se pomocí Dijkstrova algoritmu pro každý uzel spočítají vzdálenosti od tohoto uzlu. Výstupem bude tedy matice vzdáleností mezi všemi uzly.
Zde na obrázku byla nalezena minimální cesta z uzlu A. Vzdálenosti od uzlu A uvedené na obrázku v závorce jsou přehodnocené, a vzdálenosti uvedené před závorkou jsou původní.
Například délka cesty z A do C v přehodnoceném grafu je: 0+1+0 = 1. Zpětným přehodnocením podle:
se získá délka v původním grafu jako: 1-(0)+(-3) = -2. Tato délka skutečně odpovídá délce cesty z A do C v původně ohodnoceném grafu.
Složitost
Časová složitost Pro řídké grafy předpokládáme, že počet hran |H| v úplném grafu o |U| uzlech platí, že:
Bellmanův-Fordův algoritmus má časovou složitost . Je tedy v kontextu Johnsonova algoritmu zanedbatelný. Stejně tak přehodnocení hran je se složitostí zanedbatelné.
Časově nejnáročnější složkou je opakovaný Dijkstrův algoritmus. V řídkých grafech lze efektivně implementovat prioritní frontu v Dijkstrově algoritmu pomocí Fibonacciho haldy. Taková implementace Dijkstrova algoritmu má pak časovou složitost pro výpočet vzdáleností z jednoho uzlu.
Celková asymptotická složitost Johnsonova algoritmu je tedy:
Floydův–Warshallův algoritmus řeší problém vyhledání nejkratších cest mezi všemi uzly grafu s časovou složitostí . Bellmanův-Fordův algoritmus pro všechny uzly pak se složitostí .
Paměťová složitost Paměťová složitost Johnsonova algoritmu je . Zapotřebí je pouze matice vzdáleností mezi všemi uzly, případně navíc matice předchůdců.
Implementace Ukázková implementace v Javě. K uložení vzdáleností se symbolicky používá mapa <Uzel z, Uzel do> → int.
// Ukazkova implementace Johnsonova algoritmu // v 'symbolicke' Jave Vzdalenosti2D<Uzel, Uzel> Johnson(Graf G){
// Rozsireni grafu o uzel Q Uzel q = new Uzel(); G.pridejUzel(q); for(Uzel b : G.uzly()) G.pridejHranu(new Hrana(b,q));
// Bellman-Ford z bodu Q Vzdalenosti<Uzel> bf = BellmanFord(G, q); if (bf == null) // Bellman-Ford nalezl zaporny cyklus return null; else { // Odstraneni uzlu Q G.odeberUzel(q);
// Prehodncoeni hran for(Hrana h : G.hrany()) h.hodnota = h.hodnota + bf.vzdalenost(h.from()) - bf.vzdalenost(h.to());
// Dijkstruv algoritmus pro vsechny uzly Vzdalenosti2D<Uzel, Uzel> vz = new Vzdalenosti2D<Uzel, Uzel>(); for(Uzel u : G.uzly()) Dijkstra(G, u, vz); // Ulozi do vystupni struktury vzdalenosti z bodu u
// Zpetne prehodnoceni for(Uzel u : G.uzly()){ for(Uzel v : G.uzly()){ vz.setHodnota(u, v, vz.hodnota(u,v) - bf.vzdalenost(u) + bf.vzdalenost(v));
return vz;
Související články Bellmanův–Fordův algoritmus Dijkstrův algoritmus Floydův–Warshallův algoritmus Cesta v grafu
Externí odkazy
Literatura
Kategorie:Vzdálenosti v grafu Kategorie:Grafové algoritmy Kategorie:Vyhledávací algoritmy