Algorytm Bellmana-Forda

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

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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

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