Algorytm Johnsona

Algorytm Johnsona

Rodzaj	problem najkrótszej ścieżki
Struktura danych	graf skierowany
Złożoność
Czasowa	$O(|V|^{2}\log |V|+|V||E|)$

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

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

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Wyd. VII. Wydawnictwo Naukowe PWN, 2019, s. 714-719.