Алгоритм Беллмана-Форда решает задачу о кратчайших путях из одной вершины для случая, когда весам ребер разрешено быть отрицательными.
Алгоритм возвращает значение TRUE, если в графе нет цикла отрицательного веса, достижимого из исходной вершины, и FALSE, если таковой цикл имеется.
В первом случае алгоритм находит кратчайшие пути и их веса; во втором случае кратчайших путей для некоторых вершин не существует
Алгоритм производит релаксацию ребер, пока все значения d[v] не сравняются с d( s,v).
BELLMAN-FORD (G, w, s)
1 INITIALIZE-SINGLE-SOURCE (G,s)
2 for i ¬ 1 to ôV[G]ô-1
3 do for (для) каждого ребра (u,v) Î E[G]
4 do RELAX (u,v,w)
5 for (для) каждого ребра (u,v) Î E[G]
6 do if d[v] > d[u] + w (u,v)
7 then return FALSE
8 returnTRUE
Оценка времени работы алгоритма
Стоимость инициализации в строке 1 есть O(V).
Общее число релаксаций есть O(VE).
Стоимость цикла в строках 5-8 есть O(E).
Суммарное время работы алгоритма есть O(VE).
Исполнение алгоритма Беллмана-Форда
Исходный граф
Последовательность просмотра ребер при релаксации
(u,v), (u,x), (u,y), (v,u), (x,v), (x,y), (y,v), (y,z), (z,u), (z,x)
Исходная вершина – z
Шаг 1
Шаг 2
Шаг 3
Шаг 4
Проверка достижимости циклов отрицательного веса
u → v1
v → v2
| v1 | v2 | d[v1] | d[v2] | w(v1, v2) | (1)+(3) | (2) ? (4) |
| (1) | (2) | (3) | (4) | |||
| u | v | > | ||||
| u | x | < | ||||
| u | y | -2 | -4 | -2 | = | |
| v | u | -2 | = | |||
| x | v | -3 | = | |||
| x | y | -2 | < | |||
| y | v | -2 | < | |||
| y | z | -2 | = | |||
| z | u | < | ||||
| z | x | = |