Article on other languages:
- Bellman-Fordův_algoritmus
- Bellman-Ford-Algorithmus
- Bellman-Ford_algorithm
- Algoritmo_de_Bellman-Ford
- الگوریتم_بلمن-فورد
- Algorithme_de_Ford-Bellman
- 벨만-포드_알고리즘
- Algoritmo_di_Bellman-Ford
- אלגוריתם_בלמן-פורד
- ბელმან-ფორდის_ალგორითმი
- Bellmana-Forda_algoritms
- Algoritmo_de_Bellman-Ford
- Алгоритм_Беллмана_—_Форда
- Thuật_toán_Bellman-Ford
- 贝尔曼-福特算法
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).
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