Алгоритм Беллмана—Форда
Алгоритм Беллмана—Форда - алгоритм пошуку найкоротшого шляху в зваженому графі. За час O (| V | × | E |) алгоритм знаходить найкоротші шляхи від однієї вершини графа до всіх інших. На відміну від алгоритму Дейкстри, алгоритм Беллмана—Форда допускає ребра з негативним вагою. Запропоновано незалежно Річардом Беллманом і Лестером Фордом (англ. Lester Randolph Ford, Jr.).
Зміст |
Історія [ред.]
Алгоритм маршрутизації RIP (алгоритм Беллмана - Форда) був вперше розроблений в 1969 році, як основний для мережі ARPANET.
Формулювання задачі [ред.]
Дано орієнтований або неорієнтований граф G зі зваженими ребрами. Довжиною шляху назвемо суму ваг ребер, що входять в цей шлях. Потрібно знайти найкоротші шляхи від виділеної вершини s до всіх вершин графа.
Помітимо, що найкоротших шляхів може не існувати. Так, у графі, що містить цикл з негативним сумарною вагою, існує як завгодно короткий шлях від однієї вершини цього циклу до іншої (кожен обхід циклу зменшує довжину шляху). Цикл, сума ваг ребер якого негативна, називається негативним циклом.
Рішення задачі на графі без негативних циклів [ред.]
Вирішимо поставлене завдання на графі, в якому свідомо немає негативних циклів.
Для знаходження найкоротших шляхів від однієї вершини до всіх інших, скористаємося методом динамічного програмування. Побудуємо матрицю Aij, елементи якої будуть позначати наступне: Aij - це довжина найкоротшого шляху з s у i, що містить не більше j ребер.
Шлях, що містить 0 ребер, існує тільки до вершини s. Таким чином, Ai0 дорівнює 0 при i = s, і плюс нескінченності в іншому випадку.
Тепер розглянемо всі шляхи з s в i, що містять рівно j ребер. Кожен такий шлях є шлях з j - 1 ребра, до якого додано останнє ребро. Якщо про шляхи довжини j - 1 всі дані вже підраховано, то визначити j-й стовпець матриці не складає труднощів.
Граф з негативним циклом [ред.]
Алгорітм Беллмана - Форда дозволяє дуже просто визначити, чи існує в графі G негативний цикл, досяжний з вершини s. Досить зробити зовнішню ітерацію циклу не | V | - 1, a рівно | V | разів. Якщо при виконанні останньої ітерації довжина найкоротшого шляху до будь-якої вершини строго зменшилася, то в графі є негативний цикл, досяжний з 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.
