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.
Działanie 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.
Przypisy
Bibliografia
Kategoria:Algorytmy grafowe Kategoria:Algorytmy wyszukiwania