Czytaj więcej"/> Drukuj

Algorytm Johnsona - algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie \[O (|V|^2lg|V| + |V||E|) \] (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych o kopce 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. W algorytmie Johnsona jako podprogramy używane są algorytmy Dijkstry i Bellmana-Forda.
Materiał wydrukowany z portalu zgapa.pl dnia 2020-08-10 17:13:46