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

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

Предназначение	поиск кратчайшего пути в графе
Структура данных	граф
Худшее время	<math>\Theta (
Лучшее время	<math>\Theta (
Затраты памяти	<math>\Theta (

Алгоритм Беллмана-Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время 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 рёбер. Каждый такой путь есть путь из <math>j-1</math> ребра, к которому добавлено последнее ребро. Если про пути длины <math>j-1</math> все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

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

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

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

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

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

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

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

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

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

while <math>j > 0</math>
  <math>p[j] \gets i</math>
  <math>i \gets P_{ij}</math>
  <math>j \gets j - 1</math>
return p

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

Алгоритм Беллмана-Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не <math>|V| - 1</math>, a ровно <math>|V|</math> раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из 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/algo/ford_bellman Реализация алгоритма Форда-Беллмана на e-maxx.ru]
• [e-maxx.ru/algo/negative_cycle Реализация алгоритма Поиска отрицательного цикла на e-maxx.ru]
• [books.google.ru/books?id=NLngYyWFl_YC&lpg=PA639&ots=BxRrCy6fB5&dq=bellman%20ford%20algorithm%20cormen&hl=ru&pg=PA589#v=onepage&q=bellman%20ford%20algorithm%20cormen&f=false Псевдокод из книги «Introduction To Algorithms» (Thomas H Cormen,Charles E Leiserson,Ronald L Rivest,Clifford Stein)]

Отрывок, характеризующий Алгоритм Беллмана — Форда

Он не договорил. В это время в воздухе послышался свист; ближе, ближе, быстрее и слышнее, слышнее и быстрее, и ядро, как будто не договорив всего, что нужно было, с нечеловеческою силой взрывая брызги, шлепнулось в землю недалеко от балагана. Земля как будто ахнула от страшного удара.
В то же мгновение из балагана выскочил прежде всех маленький Тушин с закушенною на бок трубочкой; доброе, умное лицо его было несколько бледно. За ним вышел владетель мужественного голоса, молодцоватый пехотный офицер, и побежал к своей роте, на бегу застегиваясь.


Князь Андрей верхом остановился на батарее, глядя на дым орудия, из которого вылетело ядро. Глаза его разбегались по обширному пространству. Он видел только, что прежде неподвижные массы французов заколыхались, и что налево действительно была батарея. На ней еще не разошелся дымок. Французские два конные, вероятно, адъютанта, проскакали по горе. Под гору, вероятно, для усиления цепи, двигалась явственно видневшаяся небольшая колонна неприятеля. Еще дым первого выстрела не рассеялся, как показался другой дымок и выстрел. Сраженье началось. Князь Андрей повернул лошадь и поскакал назад в Грунт отыскивать князя Багратиона. Сзади себя он слышал, как канонада становилась чаще и громче. Видно, наши начинали отвечать. Внизу, в том месте, где проезжали парламентеры, послышались ружейные выстрелы.
Лемарруа (Le Marierois) с грозным письмом Бонапарта только что прискакал к Мюрату, и пристыженный Мюрат, желая загладить свою ошибку, тотчас же двинул свои войска на центр и в обход обоих флангов, надеясь еще до вечера и до прибытия императора раздавить ничтожный, стоявший перед ним, отряд.
«Началось! Вот оно!» думал князь Андрей, чувствуя, как кровь чаще начинала приливать к его сердцу. «Но где же? Как же выразится мой Тулон?» думал он.
Проезжая между тех же рот, которые ели кашу и пили водку четверть часа тому назад, он везде видел одни и те же быстрые движения строившихся и разбиравших ружья солдат, и на всех лицах узнавал он то чувство оживления, которое было в его сердце. «Началось! Вот оно! Страшно и весело!» говорило лицо каждого солдата и офицера.
Не доехав еще до строившегося укрепления, он увидел в вечернем свете пасмурного осеннего дня подвигавшихся ему навстречу верховых. Передовой, в бурке и картузе со смушками, ехал на белой лошади. Это был князь Багратион. Князь Андрей остановился, ожидая его. Князь Багратион приостановил свою лошадь и, узнав князя Андрея, кивнул ему головой. Он продолжал смотреть вперед в то время, как князь Андрей говорил ему то, что он видел.
Выражение: «началось! вот оно!» было даже и на крепком карем лице князя Багратиона с полузакрытыми, мутными, как будто невыспавшимися глазами. Князь Андрей с беспокойным любопытством вглядывался в это неподвижное лицо, и ему хотелось знать, думает ли и чувствует, и что думает, что чувствует этот человек в эту минуту? «Есть ли вообще что нибудь там, за этим неподвижным лицом?» спрашивал себя князь Андрей, глядя на него. Князь Багратион наклонил голову, в знак согласия на слова князя Андрея, и сказал: «Хорошо», с таким выражением, как будто всё то, что происходило и что ему сообщали, было именно то, что он уже предвидел. Князь Андрей, запихавшись от быстроты езды, говорил быстро. Князь Багратион произносил слова с своим восточным акцентом особенно медленно, как бы внушая, что торопиться некуда. Он тронул, однако, рысью свою лошадь по направлению к батарее Тушина. Князь Андрей вместе с свитой поехал за ним. За князем Багратионом ехали: свитский офицер, личный адъютант князя, Жерков, ординарец, дежурный штаб офицер на энглизированной красивой лошади и статский чиновник, аудитор, который из любопытства попросился ехать в сражение. Аудитор, полный мужчина с полным лицом, с наивною улыбкой радости оглядывался вокруг, трясясь на своей лошади, представляя странный вид в своей камлотовой шинели на фурштатском седле среди гусар, казаков и адъютантов.
– Вот хочет сраженье посмотреть, – сказал Жерков Болконскому, указывая на аудитора, – да под ложечкой уж заболело.
– Ну, полно вам, – проговорил аудитор с сияющею, наивною и вместе хитрою улыбкой, как будто ему лестно было, что он составлял предмет шуток Жеркова, и как будто он нарочно старался казаться глупее, чем он был в самом деле.
– Tres drole, mon monsieur prince, [Очень забавно, мой господин князь,] – сказал дежурный штаб офицер. (Он помнил, что по французски как то особенно говорится титул князь, и никак не мог наладить.)
В это время они все уже подъезжали к батарее Тушина, и впереди их ударилось ядро.
– Что ж это упало? – наивно улыбаясь, спросил аудитор.
– Лепешки французские, – сказал Жерков.
– Этим то бьют, значит? – спросил аудитор. – Страсть то какая!
И он, казалось, распускался весь от удовольствия. Едва он договорил, как опять раздался неожиданно страшный свист, вдруг прекратившийся ударом во что то жидкое, и ш ш ш шлеп – казак, ехавший несколько правее и сзади аудитора, с лошадью рухнулся на землю. Жерков и дежурный штаб офицер пригнулись к седлам и прочь поворотили лошадей. Аудитор остановился против казака, со внимательным любопытством рассматривая его. Казак был мертв, лошадь еще билась.