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 G = . Ohodnocení hran označíme jako w(h), h\in H. 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. +more 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í \widehat{w}(h) neobsahovalo záporné hodnoty. Přehodnocení hran w(h)\rightarrow \widehat{w}(h) zachovává nejkratší cesty mezi všemi dvojicemi uzlů. (Hrana h je hrana z uzlu ui do uzlu uj. ) {{Vzorec|\widehat{w}(u_i, u_j) = w(u_i, u_j) + h(u_i) - h(u_j)}} * 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 \widehat{w}-vzdálenosti vygenerované Dijkstrovým algoritmem. (Zpětná transformace funguje i na cesty z ui do uj. ) {{Vzorec|w(u_i, u_j) = \widehat{w}(u_i, u_j) - h(u_i) + h(u_j)}}.

Příklad

Příklad Johnsonova algoritmu - inicializace. +more	Ří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.
Příklad Johnsonova algoritmu - Bellmanův-Fordův algoritmus hledání nejkratších cest z uzlu Q.	{
u	A
h(u)	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. +more Kratší cesta pak může být jedině záporná. |- |Příklad Johnsonova algoritmu - přehodnocení hran. |

h	A→B	B→C	B→E	C→D	D→A	E→C
w(h)	-2	4	3	2	2	-3
\widehat{w}(h)	0	5	1	0	1	0

Hrany grafu byly přehodnoceny podle vztahu:.

\widehat{w}(u_i, u_j) = w(u_i, u_j) + h(u_i) - h(u_j).

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. |- |+morepng|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:

:w(u_i, u_j) = \widehat{w}(u_i, u_j) - h(u_i) + h(u_j)

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: |H|\ll |U|\cdot(|U|-1) \simeq

U

^2

Bellmanův-Fordův algoritmus má časovou složitost \mathcal{O}(|U|\cdot |H|). Je tedy v kontextu Johnsonova algoritmu zanedbatelný. +more Stejně tak přehodnocení hran je se složitostí \mathcal{O}(|H|) 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. +more Taková implementace Dijkstrova algoritmu má pak časovou složitost \mathcal{O}(|U|\cdot log_2(|U|) + |H|) pro výpočet vzdáleností z jednoho uzlu.

Celková asymptotická složitost Johnsonova algoritmu je tedy:

:\mathcal{O}({\left|U\right|}^{2}\cdot log_{2}{\left(\left|U\right|\right)} + \left|U\right|\left|H\right|)

Floydův-Warshallův algoritmus řeší problém vyhledání nejkratších cest mezi všemi uzly grafu s časovou složitostí \mathcal{O}(|U|^3). Bellmanův-Fordův algoritmus pro všechny uzly pak se složitostí \mathcal{O}(

U

^2|H|).

Paměťová složitost

Paměťová složitost Johnsonova algoritmu je \mathcal{O}(

U

^2). 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 → int.

// Ukazkova implementace Johnsonova algoritmu // v 'symbolicke' Jave Vzdalenosti2D 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 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 vz = new Vzdalenosti2D; 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