Algorytm Bellmana-Forda.html |
| | | ca | | | de | | | en | | | es | | | fr | | | it | | | nl | | | no | | | pl | | | pt | | | ru | | | ro | | | fi | | | sv | | | tr | | | vo | | |
| |  |
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ę du 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