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

Алгоритм Беллмана — Форда
Клас	Задача про найкоротший шлях (для зважених орієнтованих графів)
Структура даних	граф
Найгірша швидкодія
Просторова складність у найгіршому випадку

Алгоритм Беллмана—Форда — алгоритм пошуку найкоротшого шляху в зваженому графі. Знаходить найкоротші шляхи від однієї вершини графу до всіх інших. На відміну від алгоритму Дейкстри, алгоритм Беллмана—Форда допускає ребра з негативною вагою. Запропоновано незалежно Річардом Беллманом і Лестером Фордом.

Історія

Алгоритм носить ім'я двох американських вчених: Річарда Беллмана (Richard Bellman) і Лестера Форда (Lester Ford). Форд фактично винайшов цей алгоритм в 1956 році при вивченні іншої математичної задачі, підзадача якої звелася до пошуку найкоротшого шляху в графі, і Форд зробив начерк остаточного вирішення завдання цього алгоритму. Беллман в 1958 р. опублікував статтю, присвячену конкретно завданню знаходження найкоротшого шляху, і в цій статті він чітко сформулював алгоритм у тому вигляді, в якому він відомий нам зараз.

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

Формулювання задачі

Дано орієнтований або неорієнтований граф $G(V,E)$ з ваговою функцією $w:E\to \mathbb {R} .$ Вагою $w(p)$ шляху $p=\langle v_{0},v_{1},\dots ,v_{k}\rangle$ назвемо суму ваг ребер, що входять в цей шлях: $w(p)=\sum _{i=1}^{k}w(v_{i-1},v_{i}).$

Вхідними даними для алгоритму є граф $G,$ вагова функція $w,$ та стартова вершина $s.$ Потрібно знайти найкоротші шляхи від вершини $s$ до всіх вершин графу. Алгоритм Беллмана-Форда повертає логічне значення, яке вказує на те, чи міститься в графі цикл з негативною вагою, досяжний з витоку. Якщо такий цикл існує у графі $G,$ алгоритм повідомляє, що найкоротших шляхів не існує. Якщо ж таких циклів немає, алгоритм видає найкоротші шляхи і їх вагу.

Сам алгоритм Форда-Беллмана представляє з себе кілька фаз. На кожній фазі проглядаються всі ребра графу, і алгоритм намагається справити релаксацію (relax, ослаблення) уздовж кожного ребра $(u,v)$ ваги $w(u,v)$ . Релаксація вздовж ребра — це спроба поліпшити значення $v.d$ значенням $v.u+w(u,v)$ . Фактично це означає, що ми намагаємося поліпшити значення для вершини $v,$ користуючись ребром $(u,v)$ і поточним значенням для вершини $u$ . Стверджується, що достатньо $|G.V|-1$ фази алгоритму, щоб коректно порахувати довжини всіх найкоротших шляхів у графі (цикли негативної ваги відсутні). Для недосяжних вершин відстань $v.d$ залишиться нескінченністю.

Псевдокод

 // Ініціалізація
 для кожної вершини  $v\in G.V$ 
      $v.d=\infty$ 
      $v.\pi =NIL$ 
  $s.d=0$ 
 // Основна частина
 для  $i=1$  до  $|G.V|-1$  
     для кожного ребра  $(u,v)\in G.E$ 
         якщо  $v.d>u.d+w(u,v)$ 
              $v.d=u.d+w(u,v)$ 
              $v.\pi =u$  // зберігаємо попередню вершину
 // Перевірка на наявність циклів з від'ємною вагою
 для кожного ребра  $(u,v)\in G.E$ 
     якщо  $v.d>u.d+w(u,v)$ 
         повернути ХИБА
 повернути ІСТИНА

Оцінка складності

Якщо граф заданий списком ребер: ініціалізація потребує $O(V)$ часу, кожен з $|V|-1$ проходів потребує $O(E)$ часу, прохід по усім ребрам для перевірки наявності негативного циклу займає $O(E)$ часу. Отже алгоритм працює за $O(VE)$ часу.

Якщо граф заданий матрицею суміжності, то алгоритм буде виконуватись за $O(E^{3})$ часу.

Література

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 [Архівовано 7 вересня 2011 у Wayback Machine.]
Реалізація алгоритму пошуку негативного циклу на e-maxx.ru [Архівовано 7 вересня 2011 у Wayback Machine.]