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^[1].

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

Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja ${\displaystyle |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 ${\displaystyle O(|V|\cdot |E|)}$^[1].

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

Na algorytmie Bellmana-Forda bazuje protokół RIP - Routing Information Protocol^[2].

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