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.
Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja 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 .
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
Przypisy
Linki zewnętrzne Opis algorytmu na algorytm.org Przykładowe wykonanie algorytmu krok po kroku [dostęp 2025-12-20].
Bellmana-Forda