Algorytm Johnsona

REKLAMA

Programowanie wspomagane sztuczną inteligencją. Lepsze planowanie, kodowanie, testowanie i wdrażanie
−40%47,40 zł
Algorytmy
−40%47,40 zł

Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.

Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.

Opis działania algorytmu

Na początku wykonujemy algorytm Bellmana-Forda w wersji z dodatkowym wierzchołkiem. W ten sposób weryfikujemy, czy graf nie zawiera ujemnych cykli. Oznaczmy odległości znalezione przez ten algorytm jako hi (i jest wybranym wierzchołkiem grafu).

Następnie trzeba zmodyfikować wagi krawędzi tak, aby pozbyć się wartości ujemnych, a jednocześnie nie zmienić optymalnych tras pomiędzy wierzchołkami. W tym celu możemy skorzystać ze wzoru k'i,j = ki,j + hi − hj, gdzie ki,j jest wagą krawędzi prowadzącej z wierzchołka i do wierzchołka j, a wartości hi i hj są rezultatami wykonania algorytmu Bellmana-Forda.

Teraz nie mamy już krawędzi o ujemnych wagach, możemy zatem wykonać algorytm Dijkstry. Algorytm ten wykonujemy n razy, za każdym razem biorąc inny wierzchołek jako źródłowy. W ten sposób znajdujemy najkrótsze ścieżki pomiędzy każdą parą wierzchołków.

Na końcu musimy odtworzyć oryginalne odległości. W tym celu korzystamy ze wzoru: di,j = d'i,j − hi + hj, gdzie d'i,j jest długością ścieżki z wierzchołka i do wierzchołka j wyznaczoną przez algorytm Dijkstry.

Bibliografia

  • A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012, ISBN 9788373359383.
Ocena: +6 Tak Nie
Liczba głosów: 6.

Dodano: 12 sierpnia 2017 13:55, ostatnia edycja: 30 stycznia 2019 15:53.

REKLAMA

Zobacz też

Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).

→ Czytaj całość

Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.

Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.

→ Czytaj całość

Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.

→ Czytaj całość
Polityka prywatnościKontakt