Johnsonův algoritmus
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
Ří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. | ||||||||||||||||||||||
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á. | ||||||||||||||||||||||
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. | ||||||||||||||||||||||
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
- Obrázky, zvuky či videa k tématu Johnsonův algoritmus na Wikimedia Commons
Literatura
- KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5.
Média použitá na této stránce
Příklad Johnsonova algoritmu část 4.
Příklad Johnsonova algoritmu část 1.
Příklad Johnsonova algoritmu část 3.
Příklad Johnsonova algoritmu část 2.