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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

while $j > 0$
  $p[j] \gets i$
  $i \gets P_{ij}$
  $j \gets j - 1$
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.

См. также

• Исследование операций

Ссылки

• Реализация алгоритма Форда–Беллмана на e-maxx.ru
• Реализация алгоритма Поиска отрицательного цикла на e-maxx.ru
• Псевдокод из книги "Introduction To Algorithms" (Thomas H Cormen,Charles E Leiserson,Ronald L Rivest,Clifford Stein)