Алгоритм Беллмана–Форда

Алгоритм Беллмана–Форда, алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Алгоритм маршрутизации RIP (А.Б.–Ф.) был впервые разработан в 1969 году, как основной для сети ARPANET.

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.

Для нахождения кратчайших путей от одной вершины до всех остальных, воспользуемся методом динамического программирования. Построим матрицу Aij, элементы которой будут обозначать следующее: Aij — это длина кратчайшего пути из s в i, содержащего не более j рёбер.

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и +∞ в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из j − 1 ребра, к которому добавлено последнее ребро. Если про пути длины j − 1 все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов:

for

do

for to | V | − 1

do for

if d[v] > d[u] + w(u,v)

then

return d

Здесь V — множество вершин графа G, E — множество его рёбер, а w — весовая функция, заданная на ребрах графа.

Внешний цикл выполняется | V | − 1 раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.

Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицуPij.

Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).

Теперь А.Б.–Ф.  выглядит так:

for

for to | V | − 1

do

for to | V | − 1

do for

if Avi > Au,i − 1 + w(u,v)

then

После выполнения этого алгоритма элементы Ai,j содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:

while j > 0

return p

А.Б.–Ф. позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не | V | − 1, a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию. Можно отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит можно сделать выход из цикла.

Литература:

• R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87-90, 1958.

• L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.