: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

A L G O R Y T M   B E L L M A N A - F O R D A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Algorytm Bellmana-Forda służy do wyznaczenia minimalnych kosztów dojścia od ustalonego wierzchołka grafu skierowanego do wszystkich jego pozostałych wierzchołków. Graf może zawierać krawędzie o ujemnym koszcie, ale nie powinien zawierać cyklu o ujemnym koszcie - po takim cyklu można poruszać się wielokrotnie, a tym samym obniżać koszt drogi do minus nieskończości.

Niech ustalonym wierzchołkiem źródłowym będzie wierzchołek 1.
Przed d(i, j) oznaczamy koszt krawędzi (i, j), jeśli krawędź taka nie istnieje to przyjmujemy, że jej koszt jest nieskończony.
Wówczas można przyjąć, że minimalny koszt dojścia D(j) od wierzchołka 1 do wierzchołka j jest równy d(1, j).

Niech v będzie dowolnym wierzchołkiem grafu różnym od wierzchołka źródłowego 1. Jeśli istnieje krawędź (1, v), to koszt dojścia do wierzchołka v równy D(v) posiada już przypisaną wartość d(1, v), która wcale nie musi być najmniejszym kosztem dojścia, ale jest określona, tzn. różna od nieskończoności.

Stawiamy pytanie, czy do wierzchołka v można dojść ścieżką długości 2, przechodzącą przez pewnien inny wierzchołek u, czyli ścieżką postaci 1-i-v. Możemy to sprawdzić pisząc pętlę, która oszacuje koszty wszystkich możliwych ścieżek długości 2 postaci 1-i-v, pamiętając o tym, że nawet jeśli nie istnieją krawędzie (1, i) lub (i, v) to niczemu to nie przeszkadza - koszt takiej ścieżki będzie równy nieskończoności:

For i:=1 To n Do
  If D(i)+d[i, v]<D(v) Then D(v):=D(i)+d[i, v];

Po wykonaniu takiej pętli koszt dojścia do wierzchołka v, czyli D(v), będzie równy albo kosztowi krawędzi d[1, v], albo kosztowi pewnej znalezionej ścieżki długości 2 o mniejszym koszcie. Można zatem powiedzieć, że wyznaczony został najmniejszy możliwy koszt dojścia do wierzchołka v po ścieżce o maksymalnej długości 2. Nie musi to być ścieżka najtańsza, ale na pewno jest najtańszą ścieżką z wszystkich ścieżek o długości nie większej niż 2.

Algorytm Bellmana-Forda wyznacza minimalne koszty dojścia do wszystkich wierzchołków po ścieżkach o maksymalnej długości 2, co uzyskamy dopisując jedną pętlę For:

  • Dla wszystkich węzłów j od 2 do n:

    • znajdź najtańszą ścieżkę długości 2 prowadzącą do wierzchołka j

For j:=2 To n Do
  For i:=2 To n Do
    If D(i)+d[i, j]<D(j) Then D(j):=D(i)+d[i, j];

Pozostaje teraz postawić pytanie co wykonałby taki kod:

For j:=2 To n Do
  For i:=2 To n Do
    If D(i)+d[i, j]<D(j) Then D(j):=D(i)+d[i, j];
For j:=2 To n Do
  For i:=2 To n Do
    If D(i)+d[i, j]<D(j) Then D(j):=D(i)+d[i, j];

Pierwsze dwie pętle wyznaczą minimalne koszty dojścia do wierzchołków po ścieżkach o maksymalnej długości 2. Jeśli graf zawiera ścieżkę 1-u-v-z to podczas wykonywania drugich pętli For dla j=z i i=v będą określone wartości D(v) oraz d[v, z], a tym samym znalezione zostanie mniejsze oszacowanie kosztu dojścia do wierzchołka z. Powtórne wykonanie wyznaczy minimalne koszty dojścia do wszystkich wierzchołków po ścieżkach o maksymalnej długości 3.

Ponieważ każda prosta ścieżka w grafie ma długość co najwyżej n-1 powtarzając obie pętle n-1 razy znajdziemy minimalne koszty dojścia do wszystkich wierzchołków grafu.

For k:=1 To n-1 Do
  For j:=2 To n Do
    For i:=2 To n Do
      If D(i)+d[i, j]<D(j) Then D(j):=D(i)+d[i, j];

Złożoność obliczeniowa
Przy reprezentacji grafu za pomocą macierzy sąsiedztwa całość algorytmu tworzą trzy pętle For, co daje złożoność rzędu O(n3).
Jeśli graf zapamiętamy za pomocą listy krawędzi, to dwie pętle For przebiegające po wszystkich wierzchołkach zastąpić można jedną przebiegajacą po wszystkich krawędziach. Złożóność obliczeniowa będzie wówczas rzędu O(V*E).