Алгоритм Беллмана-Форда – це алгоритм, який обчислює найкоротші шляхи від однієї вихідної вершини до всіх інших вершин в зваженому орієнтованому графі. Безумовно, він являється повільнішим, ніж алгоритм Дейкстри для тієї ж задачі, але більш універсальний, оскільки здатний обробляти графи, в яких вага деяких ребер приймає від’ємного значення. Алгоритм зазвичай називають на честь двох його розробників, Річарда Беллмана і Лестера Форда, які опублікували його у 1958 та 1956 роках відповідно. Тим не менш, Едвард Форест Мур також опублікував даний алгоритм у 1957 році, і з цієї причини його також іноді називають алгоритмом Беллмана-Форда-Мура.
Різниця в кінцеваому результаті між алгоритмом Беллмана-Форда та алгоритмом Дейкстри
Як уже зазначалося вище, алгоритм Беллмана-Форда підходить для роботи з графами, що мають ребра з від’ємною вагою. Однак, якщо граф містить «від’ємний цикл», тобто цикл, сума ваги ребер якого дорівнює від’ємному значенню, тоді, для даного графа, не існує дерева найкоротших шляхів (будь-який шлях такого типу може бути покращений ще одним проходом через ребра, що утворюють від’ємний цикл). В такому випадку алгоритм Беллмана-Форда може виявити цикли від’ємної довжини і повідомити про їх існування, але він не може дати правильну відповідь, тобто знайти найкоротший шлях, якщо від’ємний цикл досяжний з вершини джерела.
Запишемо алгоритм Беллмана-Форда більш детально. Для цього, розглянемо деякий орієнтований граф із зваженими ребрами, який не містить циклів від’ємної довжини. І припустимо, що потрібно знайти найкоротші шляхи від виділеної вершини до всіх інших вершин даного графа:
- Перед початком виконання алгорітму всі вершини графа вважаються непройденими, а ребра – не переглянутими. Кожній вершині в ході виконання алгоритму присвоюється число , рівне довжині найкоротшого шляху з вершини у вершину , що включає тільки пройдені вершини. На першому кроці покладаємо і для всіх , відмінних від . Також, на даному кроці, вершині присвоюється мітка «пройдена» і покладається ( – остання з пройдених вершин).
- Для кожної з вершин графа наступним чином перерахувати величину : (де – вага ребра ). Якщо для всіх непройдених вершин , процедуру алгоритму Беллмана-Форда необхідно завершити (у вихідному графі відсутні шляхи з вершини у непройдені вершини). В іншому випадку, мітку «пройдена» необхідно присвоїти тій з вершин , для якої величина є найменшою. Крім того, ребро, що веде в обрану на даному етапі вершину вважається переглянутим (для цієї дуги досягався мінімум відповідно до виразу (1)). Після цього, поклавши , ітераційний процес продовжується далі. Відмітимо, що якщо для деякої пройденої вершини відбувається зменшення величини , то з цієї вершини і инцидентного їй переглянутого ребра відповідні мітки знімаються.
- Процедура алгоритму Беллмана-Форда завершується тільки тоді, коли всі вершини графа пройдені і коли після чергового виконання кроку номер два жодне з чисел не змінило свого значення.
Алгоритм Беллмана-Форда – приклад:
Використовуючи алгоритм Беллмана-Форда, побудувати дерево найкоротших шляхів для орієнтованого графа зображеного на наступному рисунку.
Орієнтований граф що містить ребра від’ємної довжини
Згідно з розглянутим алгоритмом, на першому кроці, мітку «пройдена» присвоїмо вершині номер один і припустимо, що . Після цього, поклавши та скориставшись формулою (1), здійснюємо перерахунок величин :
Оскільки значення довжини менше за , мітка «пройдена» присвоюється вершині «2». Разом з нею, переглянутим вважається також і ребро , з якого і складається поточне дерево найкоротших шляхів.
Виходячи з того, що переглягуті не всі вершини заданого графа, робимо перехід до кроку номер два, а саме покладаємо і виконуємо перерахунок величин :
Переглянувши отримані результати бачимо, що довжина , на даному етапі, приймає найменшого значення, тому, вершині «5» присвоюємо мітку «пройдена», а ребру – «переглянуте» (на даному етапі дерево найкоротших шляхів складається з ребер та ).
Далі, покладаємо і знову-таки виконуємо перерахунок величин :
Після цього, доповнюємо шукане дерево ребром (вершина «4» і ребро вважаються пройденою та переглянутими відповідно) і, виходячи з того, що серед вершин заданого графа не всі являються пройденими, покладаємо , після чого, продовжуємо алгоритм Беллмана-Форда далі:
З отриманих результатів бачимо, що на даному етапі мітку «пройдена» необхідно присвоїти вершині номер «3» та мітку «переглянуте» – ребру .
Виходячи з того, що всі вершини графа вважаються пройденими, покладаємо і, з метою спробувати зменшити числа , здійснюємо повернення до кроку номер два:
Оскільки мітку «пройдена» присвоїно всім вершинам графа і на попередньому кроці алгоритму жодну з величин не вдалося зменшити, процедура алгоритму Беллмана-Форда завершується.
Дерево найкоротших шляхів
Таким чином, дерево найкоротших шляхів, для заданого орієнтованого графа, складається з наступних ребер: (ребра, які, після виконання алгоритму, були помічені як переглянуті).