Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Szkoła programisty PLC. Język LAD w programowaniu sterowników przemysłowych
−30%41,30 zł
Algorytmy bez tajemnic
44,90 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Cyberwojna. Metody działania hakerów
49,00 zł
Bitcoin dla zaawansowanych. Programowanie z użyciem otwartego łańcucha bloków. Wydanie II
69,00 zł

Algorytm Johnsona

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

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

Dodano: 12 sierpnia 2017 13:55, ostatnia edycja: 10 listopada 2017 14:43.

Zobacz też

Stos (ang. Stack) – struktura danych, w której bezpośredni dostęp jest tylko do ostatnio dodanego elementu. Stos bywa określany także jako kolejka LIFO (z ang. Last In, First Out, czyli: ostatni na wejściu, pierwszy na wyjściu). Stos można sobie wyobrazić jako kilka rzeczy ułożonych „jedna na drugiej” – łatwo można wziąć tylko rzecz leżącą na samym wierzchu, gdyż pozostałe są przykryte.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną.

→ Czytaj całość
Polityka prywatnościKontakt