Algorytm Bellmana-Forda – Wikipedia, wolna encyklopedia

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

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].

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].

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 

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