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

Przypisy

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.