Algorytm Bellmana-Forda

Algorytm Bellmana-Forda – algorytm służący do wyszukiwania najkrótszych ścieżek w grafie ważonym z wierzchołka źródłowego do wszystkich pozostałych wierzchołków.

Rodzaj	problem najkrótszej ścieżki
Struktura danych	graf skierowany
Złożoność
Czasowa	$O(|V|\cdot |E|)$
Pamięciowa	$O(|V|)$

Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja $|V|-1$ razy każdej z krawędzi).

W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda działa poprawnie także dla grafów z wagami ujemnymi (nie może jednak wystąpić cykl o łącznej ujemnej wadze osiągalny ze źródła). Za tę ogólność płaci się jednak wyższą złożonością czasową. Działa on w czasie $O(|V|\cdot |E|)$.

Algorytm może być wykorzystywany także do sprawdzania, czy w grafie występują ujemne cykle osiągalne ze źródła.

Na algorytmie Bellmana-Forda bazuje protokół RIP - Routing Information Protocol.

Zapis w pseudokodzie

Dla grafu G, funkcji wagowej w i wierzchołka s otrzymamy tablicę d[u] odległości każdego wierzchołka grafu od wierzchołka s.

Bellman-Ford(G,w,s):

dla każdego wierzchołka v w V[G] wykonaj
  d[v] = nieskończone
  poprzednik[v] = niezdefiniowane
d[s] = 0
dla i od 1 do |V[G]| - 1 wykonaj
  dla każdej krawędzi (u,v) w E[G] wykonaj
    jeżeli d[v] > d[u] + w(u,v) to
      d[v] = d[u] + w(u,v)
      poprzednik[v] = u

Linki zewnętrzne

• Opis algorytmu na algorytm.org
• Przykładowe wykonanie algorytmu krok po kroku