Algorytm Johnsonaalgorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie (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].

Algorytm Johnsona
Rodzaj

problem najkrótszej ścieżki

Struktura danych

graf skierowany

Złożoność
Czasowa

Działanie

edytuj

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

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

Przypisy

edytuj

Bibliografia

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