🔴 Беллман-Форд
Найкоротші шляхи з від'ємними вагами
Прохід 0 / 6
Джерело: A
Налаштування
Керування
Статистика
Прохід / V−1
0 / 6
Статус
Готово
Релаксовано цим проходом
0
Всього релаксацій
0
Відстані
Довідка та теорія

Алгоритм Беллмана-Форда знаходить найкоротшу відстань від одного вихідного вузла до кожного іншого вузла у зваженому орієнтованому графі, і працює навіть тоді, коли деякі ваги ребер від'ємні.

Релаксація ребра

Кожне ребро (u, v) з вагою w багаторазово релаксується за правилом dist[v] = min(dist[v], dist[u] + w(u, v)). Якщо шлях через u коротший за поточну найкращу відому відстань до v, ця відстань — і попередник v — оновлюються.

Чому достатньо V−1 проходів

Найкоротший шлях, що не повторює вузлів, проходить не більше ніж V−1 ребер. Кожен повний прохід по всіх ребрах гарантує, що щонайменше ще одне ребро кожного найкоротшого шляху стає остаточним, тож після V−1 проходів усі найкоротші шляхи (за відсутності від'ємного циклу) повністю поширені.

Додатковий V-й прохід

Виконання ще одного проходу після обов'язкових V−1 перевіряє наявність від'ємних циклів: якщо хоча б одна відстань усе ще може покращитися, у графі існує від'ємний цикл, досяжний із джерела, і для його вузлів найкоротший шлях не визначений.

Складність

Беллман-Форд працює за O(V·E) часу та O(V) пам'яті. Це повільніше за алгоритм Дейкстри (O((V+E) log V)), але, на відміну від нього, Беллман-Форд толерує від'ємні ваги і вміє виявляти від'ємні цикли — жадібний вибір Дейкстри перестає працювати коректно, щойно з'являється від'ємне ребро.

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

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 11 липня 2026 р.

Алгоритм Беллмана-Форда, розроблений незалежно Річардом Беллманом (1958) та Лестером Фордом-молодшим (1956), обчислює найкоротші шляхи від одного вихідного вузла до кожної іншої вершини зваженого орієнтованого графа. На відміну від алгоритму Дейкстри, він коректно працює навіть із від'ємними вагами ребер, що робить його незамінним для таких застосувань, як виявлення валютного арбітражу та протоколи маршрутизації на кшталт RIP. Беллман-Форд — це алгоритм динамічного програмування: він багаторазово релаксує кожне ребро, замінюючи dist[v] на dist[u] + w(u,v), якщо ця сума менша, протягом рівно V−1 проходів, оскільки найдовший можливий найкоротший шлях без повторень вузлів містить не більше V−1 ребер. Додатковий, останній прохід перевіряє, чи може якась відстань усе ще зменшитися; якщо так, у графі є від'ємний цикл, досяжний із джерела, і найкоротший шлях для нього не визначений. Це дає складність O(V·E) за часом і O(V) за пам'яттю — повільніше за O((V+E) log V) Дейкстри, але значно універсальніше.

Часті запитання

Чому Беллману-Форду потрібно V−1 проходів?

Тому що найдовший можливий найкоротший шлях у графі з V вершинами (такий, що не повторює жодної вершини) може містити щонайбільше V−1 ребер. Кожен повний прохід по всіх ребрах гарантує, що щонайменше ще одне ребро вздовж кожного найкоротшого шляху стає остаточним, тож після V−1 проходів усі найкоротші відстані повністю поширені.

Як Беллман-Форд виявляє від'ємні цикли?

Після обов'язкових V−1 проходів алгоритм виконує ще один додатковий прохід по всіх ребрах. Якщо якесь ребро все ще можна релаксувати — тобто відстань усе ще зменшується — це можливо лише через від'ємний цикл, досяжний із джерела, адже звичайне дерево найкоротших шляхів на цьому етапі вже було б стабільним.

Чим Беллман-Форд відрізняється від алгоритму Дейкстри?

Обидва обчислюють найкоротші шляхи з одного джерела, але Дейкстра використовує жадібну чергу з пріоритетом і вимагає невід'ємних ваг, працюючи за O((V+E) log V). Беллман-Форд релаксує кожне ребро на кожному проході, толерує від'ємні ваги і вміє виявляти від'ємні цикли, ціною повільнішого часу роботи O(V·E).

Чи може Беллман-Форд працювати з неорієнтованими графами із від'ємними ребрами?

Ні. Будь-яке неорієнтоване ребро з від'ємною вагою еквівалентне циклу довжини два (u→v і v→u із тією самою від'ємною вагою), тож Беллман-Форд одразу позначить це як від'ємний цикл. Алгоритм розрахований на орієнтовані графи; від'ємні ваги мають сенс лише тоді, коли ребра мають напрямок.