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

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

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

Клас	Задача про найкоротший шлях (для зважених орієнтованих графів)
Структура даних	граф
Найгірша швидкодія	${\displaystyle O(|V||E|)}$
Просторова складність у найгіршому випадку	${\displaystyle O(|V|)}$

Історія

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

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

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

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

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

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

Псевдокод

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

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

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

Якщо граф заданий матрицею суміжності, то алгоритм буде виконуватись за ${\displaystyle 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.]