Algorytm Bellmana-Forda

ZębatkaNa ten temat mamy również tutorial „Algorytm Bellmana-Forda”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

Opis działania algorytmu

W trakcie wykonywania algorytmu dla każdego wierzchołka zostają wyznaczone dwie wartości: koszt dotarcia do tego wierzchołka (oznaczmy go jako di) oraz poprzedni wierzchołek na ścieżce (oznaczmy go jako pi). Na początku działania algorytmu dla wierzchołka źródłowego koszt dotarcia wynosi 0 (już tam jesteśmy), a dla każdego innego wierzchołka nieskończoność (w ogóle nie wiemy, jak się tam dostać).

Następnie dla każdej krawędzi (oznaczmy, że aktualnie analizowana krawędź ma wagę k i prowadzi z wierzchołka U do wierzchołka V) wykonujemy następującą czynność:

Jeżeli dV > dU + k, to ustawiamy wartość dV na dU + k, a wartość pV na U.

Całość (przejrzenie wszystkich krawędzi) należy powtórzyć n-1 razy, gdzie n jest liczbą wierzchołków. W każdej iteracji należy przejrzeć wszystkie krawędzie w tej samej kolejności. Jeśli w którejś iteracji nie nastąpią żadne zmiany, wykonywanie algorytmu można przerwać wcześniej.

Gdyby w n-tej iteracji nadal były zmiany, oznacza to, że graf zawiera ujemny cykl osiągalny z danego źródła. Algorytm można więc wykorzystać do wykrywania ujemnych cykli w grafie. Trzeba wówczas cały algorytm wykonać n razy, po razie dla każdego wierzchołka źródłowego.

Złożoność czasowa

Dla grafu liczącego n wierzchołków i e krawędzi złożoność pesymistyczna jest równa O(ne). Biorąc pod uwagę, że w przypadku braku krawędzi wielokrotnych liczba krawędzi jest zawsze mniejsza od n2, można powiedzieć, że złożoność czasowa algorytmu to O(n3).

Bibliografia

  1. A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012

Dodano: 30 marca 2017 19:25
Ostatnia edycja: 30 marca 2017 19:28