Алгоритм Беллмана—Форда
Алгоритм Беллмана—Форда - алгоритм пошуку найкоротшого шляху в зваженому графі. За час 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.
