Algorytm ten służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie bez cykli o ujemnej długości.
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Dla podanego grafu macierz A dla każdej pary wierzchołków u i v zawiera wagę krawędzi (u,v), przy czym jeśli krawędź (u,v) nie istnieje, to przyjmujemy, że jej waga wynosi nieskończoność i wpisujemy *.
Algorytm Forda-Bellmana w każdym kroku oblicza górne oszacowanie D(v_i) odległości od wierzchołka s do wszystkich pozostałych wierzchołków v_i. W pierwszym kroku przyjmujemy D(v_i)=A(s,v_i).
Gdy stwierdzimy, że D(v)>D(u)+A(u,v), to każdorazowo polepszamy aktualne oszacowanie i podstawiamy D(v):=D(u)+A(u,v). Algorytm kończy się, gdy żadnego oszacowania nie można już poprawić, macierz D(v_i) zawiera najkrótsze odległości od wierzchołka s do wszystkich pozostałych.

Pseudokod wygląda następująco:(n- liczba wierzchołków)

begin;
for v:=[1..n] do D(v):=A(s,v); //przyjmujemy, że najkrótszą drogą z u do v jest krawędź (u,v)
for k:=1 to (n-2) do //w (n-2) krokach można zbadać każdą drogę o (n-1) krawędziach i wybrać najkrótszą
begin
for v:=[1..n]-{s} do //odległość od s do s wynosi 0 i już się na pewno nie zmieni
for u:=[1..n] do
D(v):=min{D(v), D(u)+A(u,v)}; //wybierz krótszą drogę
end;

Algorytm można ulepszyć sprawdzając w każdej iteracji, czy coś się zmieniło od poprzedniej i jeśli nie, to można zakończyć obliczenia.
Dla pełnej jasności podam teraz prosty przykład: oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy s=1, symbol "*" oznacza nieskończoność:

Oto przebieg obliczeń:

k	D(1)	D(2)	D(3)	D(4)	D(5)	D(6)
0	0	2	4	*	*	*
1	0	2	4	2a	6b	4c
2	0	2	4	2	5d	4
3	0	2	4	2	5	4

Objaśnienia:
W pierwszym kroku (k=0) D(v_i)=A(1,v_i). Przepisujemy pierwszy wiersz macierzy wag krawędzi.
a). Pierwsze skrócenie drogi: w poprzednim kroku D(4)=*, gdyż nie istnieje krawędź od 1 do 4. Teraz jednak możemy przejść przez wierzchołek 3 (odległość od 1 do 3 wynosi 4) a następnie do 4 (waga krawędzi [3,4]=-2), długość drogi od 1 do 4 wynosi więc 4-2 = 2.
b). Podobnie jest tu, do wierzchołka 5 możemy dojść przez 2, 3, lub 6. Wybieramy oczywiście drogę o mniejszej długości:

• D(2)+A(2,5)=2+4=6 (ta wartość jest najmniejsza)
• D(3)+A(3,5)=4+3=7
• D(6)+A(6,5)=*+1 (ta wartość jest największa)

Wybieramy opcję z wierzchołkiem nr. 2.
c). Do wierzchołka 6 możemy dojść przez 4 (do którego dochodzimy przez 3) droga jest więc następująca: 1, 3, 4, 6 a jej długość wynosi D(4)+A(4,6)=2+2=4
d). Jak wynika z punktu b), do wierzchołka 5 możemy dojść także poprzez wierzchołek 6. W poprzednim kroku poznaliśmy odległość do wierzchołka 6 i nie wynosi ona już nieskończoność. Sprawdźmy więc, jaka byłaby długość drogi do wierzchołka 5 poprzez 6: D(6)+A(6,5) = 4+1 = 5. Jest to wartość mniejsza niż aktualna (6), więc znaleźliśmy krótszą drogę.
W kroku k=3 nic się nie zmieniło od kroku k=2. Kończymy obliczenia i mamy wektor najkrótszych dróg od wierzchołka s=1 do wszystkich pozostałych.
Złożoność obliczeniowa: O(n³).
Uwaga:
Dla grafów z wagami o nieujemnych wartościach lepiej jest stosować Algorytm Dijkstry.
Po znalezieniu najkrótszej odległości między wierzchołkami możemy znaleźć drogę łączącą te wierzchołki za pomocą algorytmu konstrukcji drogi.

Komentarze