Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Biblia e-biznesu 2. Nowy Testament
−30%90,30 zł
Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł
Młodzi giganci programowania. Scratch
34,90 zł
Algorytmy. Ilustrowany przewodnik
54,90 zł
Visual Studio 2017. Tworzenie aplikacji Windows w języku C#
89,00 zł

Algorytm Johnsona

REKLAMA

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.

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość

Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).

Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.

→ Czytaj całość

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość
Polityka prywatnościKontakt