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=<H,U>$ . 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. 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 u_i do uzlu u_j.)

${\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 u_i do u_j.)

$w(u_{i},u_{j})={\widehat {w}}(u_{i},u_{j})-h(u_{i})+h(u_{j})$

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.

Příklad Johnsonova algoritmu - Bellmanův-Fordův algoritmus hledání nejkratších cest z uzlu Q.

u	A	B	C	D	E
h(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á.

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.

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ý. 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. 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 <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

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.