Algorytm Johnsona

Algorytm Johnsona – algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie $O(|V{|}^2\log |V|+|V||E|)$ (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych na kopcach Fibonacciego), dla grafów rzadkich jest więc asymptotycznie szybszy od algorytmu Floyda-Warshalla. Algorytm Johnsona zwraca albo macierz wag najkrótszych ścieżek, albo informuje, że graf wejściowy ma cykl o ujemnej wadze. Algorytm Johnsona wykorzystuje algorytmy Dijkstry i Bellmana-FordaSzablon:Odn.

Działanie

Algorytm Johnsona wykonuje się w następujących krokach:

• Dodaj nowy węzeł $q$ połączony krawędziami o wagach $0$ z każdym innym wierzchołkiem grafu.
• Użyj algorytmu Bellmana-Forda startując od dodanego wierzchołka $q,$ aby odnaleźć minimalną odległość $d[v]$ każdego wierzchołka $v$ od $q.$ Jeżeli został wykryty ujemny cykl, zwróć tę informację i przerwij działanie algorytmu.
• W tym kroku przewagujemy graf tak, aby zlikwidować ujemne wagi krawędzi nie zmieniając wartości najkrótszych ścieżek. W tym celu każdej krawędzi $(u,v)$ o wadze $w(u,v)$ przypisz nową wagę $w(u,v)+d[u]-d[v].$
• Usuń początkowo dodany węzeł $q.$
• Użyj algorytmu Dijkstry dla każdego wierzchołka w grafieSzablon:Odn.

Bibliografia

• Szablon:Cytuj książkę