Algorytm Bellmana-Forda

03.10.2010 - Damian Rusak
TrudnośćTrudność

Algorytm

Podsumowując, nasz algorytm wygląda w ten sposób (zapisany w pseudokodzie z objaśnieniem):

Oznaczenia:

przyjmijmy dla uproszczenia, że wierzchołek startowy ma numer 1

$ n $ - liczba wierzchołków grafu;

$ m $ - liczba krawędzi grafu;

tablica $ C\left[1..n\right]\left[1..n\right] $ - przechowuje wagi krawędzi (jeśli krawędź między $ v $ i $ u $ ma wagę $ x $ to $ C\left[v\right]\left[u\right] = x $;

tablica $ D\left[1..n\right] $ - przechowuje najmniejsze tymczasowo obliczone odległości od startu do wierzchołków;

Linie $ 2 $ i $ 3 $ określają warunki początkowe - do wierzchołka startowego można dojść za zero, pozostałe wierzchołki nie zostały jeszcze osiągnięte. 

Pętla w $ 5 $ wykonuje się $ n-1 $ razy - w jej wnętrzu ($ 6 $) znajduje się druga pętla, która przebiega wszystkie krawędzie i próbuje je zrelaksować, wywołując funkcje RELAX (jej opis poniżej). Zgodnie z naszymi ustaleniami, $ n-1 $ iteracji to dokładnie tyle ile potrzeba.

Linie od $ 7 $ do $ 11 $ to sprawdzenie, czy w grafie wystąpił cykl ujemny - jeśli procedura SPRAWDZ-CYKL zwróci wartość TRUE, to odkryto istnienie cyklu ujemnego i wynikiem działania algorytmu jest informacja o takim cyklu. W przeciwnym przypadku obliczyliśmy najkrótsze ścieżki od wierzchołka starowego do wszystkich pozostałych.

Funkcja RELAX operuje na numerach dwóch wierzchołków - jeśli obecna odległość wierzchołka $ v $ ($ D\left[v\right] $) jest większa niż odległość dla $ u $ powiększona o koszt krawędzi $ (u,v) $, następuje jej poprawienie. W takim przypadku funkcja zwraca wartość TRUE - udało się zrelaksować. W przeciwnym wypadku wartość to FALSE - relaksacja się nie powiodła.

Funkcja SPRAWDZ-CYKL wykonuje jedną iterację relaksacji wszystkich krawędzi. Jeśli któraś z nich się powiedzie, świadczy to o obecności ujemnego cyklu (funkcja jest wywoływana już po wykonaniu $ n-1 $ iteracji relaksacji w funkcji BELLMAN-FORD).

 

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com