Algorytm Johnsona
Algorytm Johnsona – algorytm 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] .
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Działanie
edytujAlgorytm 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
edytujBibliografia
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.