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

Przypisy

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwo Naukowe PWN, 2012, s. 664–665. ISBN 978-83-01-16911-4.
2. RIP | Cisco dla początkujących. cisco.sadzer.pl. [dostęp 2017-03-31].

Linki zewnętrzne

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