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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм Беллмана—Форда
Клас Задача про найкоротший шлях (для зважених орієнтованих графів)
Структура даних Граф
Найгірша швидкодія O (|V| |E|)
Просторова складність у найгіршому випадку O (|V|)

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

Історія[ред.ред. код]

Алгоритм носить ім'я двох американських вчених: Річарда Беллмана (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)
             w.\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.

Посилання[ред.ред. код]