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

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

Формулировка задачи

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

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

Решение задачи на графе без отрицательных циклов

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

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

Путь, содержащий 0 рёбер, существует только до вершины ${\displaystyle s}$ . Таким образом, ${\displaystyle A_{i0}}$ равно 0 при ${\displaystyle i=s}$ , и ${\displaystyle +\infty }$ в противном случае.

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

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

for ${\displaystyle v\in V}$
  do ${\displaystyle d[v]\gets +\infty }$
${\displaystyle d[s]\gets 0}$
for ${\displaystyle i\gets 1}$ to ${\displaystyle |V|-1}$
  do for ${\displaystyle (u,v)\in E}$
    if ${\displaystyle d[v]>d[u]+w(u,v)}$
      then ${\displaystyle d[v]\gets d[u]+w(u,v)}$
return ${\displaystyle d}$

Здесь ${\displaystyle V}$ — множество вершин графа ${\displaystyle G}$ , ${\displaystyle E}$ — множество его рёбер, а ${\displaystyle w}$ — весовая функция, заданная на рёбрах графа (возвращает длину дуги , ведущей из вершины ${\displaystyle u}$ в ${\displaystyle v}$ ), ${\displaystyle d}$ — массив, содержащий расстояния от вершины ${\displaystyle s}$ до любой другой вершины.

Внешний цикл выполняется ${\displaystyle |V|-1}$ раз, поскольку кратчайший путь не может содержать большее число рёбер, иначе он будет содержать цикл, который точно можно выкинуть.

Вместо массива ${\displaystyle d}$ можно хранить всю матрицу ${\displaystyle A}$ , но это требует ${\displaystyle O(V^{2})}$ памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу ${\displaystyle P_{ij}}$ .

Если элемент ${\displaystyle A_{ij}}$ содержит длину кратчайшего пути из ${\displaystyle s}$ в ${\displaystyle i}$ , содержащего ${\displaystyle j}$ рёбер, то ${\displaystyle P_{ij}}$ содержит предыдущую вершину до ${\displaystyle i}$ в одном из таких кратчайших путей (ведь их может быть несколько).

Теперь алгоритм Беллмана-Форда выглядит так:

for ${\displaystyle v\in V}$
  for ${\displaystyle i\gets 0}$ to ${\displaystyle |V|-1}$
    do ${\displaystyle A_{vi}\gets +\infty }$
${\displaystyle A_{s0}\gets 0}$
for ${\displaystyle i\gets 1}$ to ${\displaystyle |V|-1}$
  do for ${\displaystyle (u,v)\in E}$
    if ${\displaystyle A_{vi}>A_{u,i-1}+w(u,v)}$
      then ${\displaystyle A_{vi}\gets A_{u,i-1}+w(u,v)}$
           ${\displaystyle P_{vi}\gets u}$

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

while ${\displaystyle j>0}$
  ${\displaystyle p[j]\gets i}$
  ${\displaystyle i\gets P_{ij}}$
  ${\displaystyle j\gets j-1}$
return p

Граф с отрицательными циклами

Алгоритм Беллмана-Форда позволяет очень просто определить, существует ли в графе ${\displaystyle G}$ отрицательный цикл, достижимый из вершины ${\displaystyle s}$ . Достаточно произвести внешнюю итерацию цикла не ${\displaystyle |V|-1}$ , a ровно ${\displaystyle |V|}$ раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из ${\displaystyle 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.

См. также

• Исследование операций
• Алгоритм Дейкстры

Ссылки