Algorytm Johnsona

REKLAMA Thinking in Java. Edycja polska. Wydanie IV
149,00 zł
Informatyka Europejczyka. Podręcznik dla szkoły podstawowej. Klasa 6
7,90 zł
Gotowanie dla geeków. Wydanie II
−30%48,30 zł
Algorytmy. Ilustrowany przewodnik
54,90 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: +2 Tak Nie
Liczba głosów: 2.

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

REKLAMA

Zobacz też

Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).
→ Czytaj całość

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Polityka prywatnościKontakt