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

Материал из Википедии — свободной энциклопедии

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

[править] Формулировка задачи

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

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

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

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

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

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

Теперь рассмотрим все пути из 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²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу P_ij.

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

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

for 
  for  to  $| V | - 1$ 
    do 

for  to  $| V | - 1$ 
  do for 
    if  $A v i > A u, i - 1 + w (u, v)$ 
      then

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

while  $j > 0$ 
  
  
  
return p

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

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