Algorytm Bellmana-Forda
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Algorytm Bellmana-Forda rozwiązuje problem najkrótszej ścieżki, tj. pozwala znaleźć ścieżkę o najmniejszej wadze pomiędzy dwoma wierzchołkami w grafie ważonym. Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja V − 1 razy każdej z krawędzi).
W odróżnieniu od algorytmu Dijkstry, poprawność algorytmu Bellmana-Forda nie opiera się na założeniu, że wagi w grafie są nieujemne (nie może jednak występować 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 O(V*E).
[edytuj] 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
Zobacz też: problem najkrótszej ścieżki, algorytm Dijkstry
