Алгоритм Беллмана-Форда (Bellman-Ford algorithm)

Алгоритм Беллмана-Форда позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным. Для заданного взвешенного ориентированного графа G = (V, Е) с истоком s и весовой функцией w : Е —» R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес.

В этом алгоритме используется ослабление, в результате которого величина d[v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути из s в v. Значение TRUE возвращается алгоритмом тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока.

Формальное описание     [вверх]

Bellman_Ford(G, w, s)
1    Initialize_Single_Source(G, s)
2    for i «- l 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    return TRUE

После инициализации в строке 1 всех значений d и prev, алгоритм осуществляет |V| — 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| — 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответству- ющее булево значение.

Оценка сложности     [вверх]

Алгоритм Беллмана-Форда завершает свою работу в течение времени O(V*E), поскольку инициализация в строке 1 занимает время O(V), на каждый из |V| — 1 проходов по ребрам в строках 2-4 требуется время в O(E), а на выполнение цикла for в строках 5-7 — время O(Е). .

Пример     [вверх ]

Визуализатор для алгоритма Беллмана-Форда.

Запустить визуализатор для алгоритма Беллмана-Форда

Выполнение алгоритма Беллмана-Форда:

На рисунке в вершинах графа показаны значения атрибутов d на каждом этапе работы алгоритма, а выделенные ребра указывают на значения предшественников: если ребро (u, v) выделено, то prev[v] = u. В рассматриваемом примере при каждом проходе ребра ослабляются в следующем порядке: (t, х), (t, у), (t, z), (x,t), (у,х), (у, z), (z,x), (z,s), (s,t), (s,y). В части а рисунка показана ситуация, сложившаяся непосредственно перед первым проходом по ребрам. В частях б-д проиллюстрирована ситуация после каждого очередного прохода по ребрам. Значения атрибутов d и prev, приведенные в части д, являются окончательными.

Если в графе, представленном выше, поменять вес дуги (1; 4) на -8, то мы получим отрицательный цикл из вершин 1-4-2 (дуги цикла отмечены красным цветом).

После окончания основных итераций алгоритма проходит проверка на наличие отрицательных циклов. Для данного графа во время проверки будет найдено ребро, которое можно ослабить, что является показателем существования цикла из дуг отрицательных весов. Цикл обнаружен, алгоритм прекращает работу.