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

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

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

Содержание 1 Формулировка задачи 2 Решение задачи на графе без отрицательных циклов 3 Граф с отрицательными циклами 4 Ссылки

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

Дан ориентированный или неориентированный граф 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 
  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 Avi > Au,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. На основе этого можно предложить следующую оптимизацию. Можно отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит можно сделать выход из цикла.

[править] Ссылки

• Реализация алгоритма Форда-Беллмана на maximal.hocomua.ru
• Реализация алгоритма Поиска отрицательного цикла на maximal.hocomua.ru

Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.