Algorytm Johnsona

Algorytm Johnsona

Rodzaj	problem najkrótszej ścieżki
Struktura danych	graf skierowany
Złożoność
Czasowa	${\displaystyle 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 ${\displaystyle 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^[1] .

Działanie

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

• Dodaj nowy węzeł ${\displaystyle q}$ połączony krawędziami o wagach ${\displaystyle 0}$ z każdym innym wierzchołkiem grafu.
• Użyj algorytmu Bellmana-Forda startując od dodanego wierzchołka ${\displaystyle q,}$ aby odnaleźć minimalną odległość ${\displaystyle d[v]}$ każdego wierzchołka ${\displaystyle v}$ od ${\displaystyle 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 ${\displaystyle (u,v)}$ o wadze ${\displaystyle w(u,v)}$ przypisz nową wagę ${\displaystyle w(u,v)+d[u]-d[v].}$
• Usuń początkowo dodany węzeł ${\displaystyle q.}$
• Użyj algorytmu Dijkstry dla każdego wierzchołka w grafie^[1] .

Przypisy

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓.

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.