Алгоритм Bellman-Ford: пошук найкоротшого шляху з від'ємними вагами
- 26 черв.
- Читати 4 хв
Уявіть граф, де деякі ребра мають від'ємну вагу. Не абстрактно, а цілком реально: наприклад, фінансова мережа, де конвертація валют через певний маршрут дає прибуток, а не витрату. Або логістика, де деякі переміщення субсидовані і знижують загальну вартість маршруту. Саме для таких задач існує Bellman-Ford — алгоритм пошуку найкоротшого шляху, який коректно працює з від'ємними вагами і вміє виявляти негативні цикли. За це він платить вищою складністю, але в задачах, де вага ребра може зменшувати вартість шляху, це єдиний правильний вибір.
Що таке Bellman-Ford
Алгоритм Беллмана-Форда — це алгоритм пошуку найкоротшого шляху від однієї вершини до всіх інших у зваженому орієнтованому графі. Він коректно працює з від'ємними вагами ребер і здатний виявляти негативні цикли, коли нескінченне проходження по циклу щоразу зменшує вартість шляху.Коли негативний цикл виявлено, алгоритм сигналізує про його наявність, але не повертає шлях. Це очікувана поведінка, адже правильного найкоротшого шляху в такому графі не існує, тому будь-який результат був би некоректним.
Алгоритм названий на честь Річарда Беллмана і Лестера Форда, які незалежно описали його в 1950-х. В основі лежить принцип динамічного програмування: найкоротший шлях до будь-якої вершини будується поступово через операцію, яку в теорії графів називають релаксацією.
Релаксація — це перевірка: чи можна покращити відому відстань до вершини v, якщо пройти через вершину u і ребро (u, v) якщо dist[u] + weight(u, v) < dist[v]: dist[v] = dist[u] + weight(u, v)
Алгоритм виконує V − 1 ітерацій, де V — кількість вершин. Чому саме стільки? Шлях без циклів може проходити максимум через V−1 ребер. Після кожної ітерації гарантовано знайдені всі шляхи завдовжки не більше k ребер, де k — номер ітерації.
Часова складність: O(V × E). Це повільніше за Дейкстру з його O((V + E) log V) на sparse-графах (розріджених), але для задач з від'ємними вагами — єдиний коректний варіант із базових алгоритмів.
Як працює алгоритм Беллмана-Форда
Початковий стан: dist[A] = 0, всі інші вершини = ∞.
Ітерація 1. Проходимо по всіх ребрах:
A→F: 0+3=3. dist[F] оновлюється до 3
A→B: 0+2=2. dist[B] оновлюється до 2
A→D: 0+5=5. dist[D] оновлюється до 5
F→B: 3+(−4)=−1. dist[B] покращується до −1
B→E: −1+1=0. dist[E] оновлюється до 0
D→E: 5+1=6. dist[E] вже 0 — не оновлюємо
E→C: 0+(−3)=−3. dist[C] оновлюється до −3
E→B: 0+1=1. dist[B] вже −1 — не оновлюємо
C→B: −3+7=4. dist[B] вже −1 — не оновлюємо
C→G: −3+4=1. dist[G] оновлюється до 1
G→D: 1+(−1)=0. dist[D] покращується до 0
Ітерація 2. Більшість значень вже оптимальні. D тепер 0 замість 5 — перевіряємо D→E: 0+1=1, але dist[E] вже 0. Нових покращень немає.
Ітерації 3–6. Жодне значення більше не змінюється.
Фінальна перевірка на негативний цикл. За V−1 ітерацій усі коректні шляхи вже знайдені — тому V-та ітерація є діагностикою: якщо хоча б одна відстань ще зменшилась, граф містить негативний цикл. У цьому графі сьома ітерація нічого не змінила — циклу немає.
Реалізація на Python
def bellman_ford(vertices, edges, source):
"""
vertices — список вершин графа
edges — список кортежів (u, v, weight)
source — початкова вершина
Повертає (distances, previous) або (None, None) якщо є негативний цикл.
"""
dist = {v: float('inf') for v in vertices}
prev = {v: None for v in vertices}
dist[source] = 0
for _ in range(len(vertices) - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
updated = True
if not updated:
break
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None, None # негативний цикл
return dist, prev
def reconstruct_path(prev, target):
path, current = [], target
while current is not None:
path.append(current)
current = prev[current]
return list(reversed(path))vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
edges = [
('A', 'F', 3), ('A', 'B', 2), ('A', 'D', 5),
('F', 'B', -4), ('B', 'E', 1), ('D', 'E', 1),
('E', 'C', -3), ('E', 'B', 1), ('C', 'B', 7),
('C', 'G', 4), ('G', 'D', -1),
]
dist, prev = bellman_ford(vertices, edges, source='A')
if dist is None:
print("Граф містить негативний цикл")
else:
for v in vertices:
path = reconstruct_path(prev, v)
print(f"A → {v}: {dist[v]:>3} шлях: {' → '.join(path)}")A → A: 0 шлях: A
A → B: -1 шлях: A → F → B
A → C: -3 шлях: A → F → B → E → C
A → D: 0 шлях: A → F → B → E → C → G → D
A → E: 0 шлях: A → F → B → E
A → F: 3 шлях: A → F
A → G: 1 шлях: A → F → B → E → C → GДе застосовують
Фінансові системи і арбітраж. Валютні курси моделюють як граф, де вага ребра — логарифм обмінного курсу. Від'ємний цикл у такому графі означає арбітражну можливість: послідовність обмінів повертає більше, ніж було вкладено. Беллман-Форд це виявляє.
Мережеві протоколи. RIP (Routing Information Protocol) — це розподілена реалізація Беллмана-Форда: кожен маршрутизатор виконує релаксацію локально, отримуючи відстані від сусідів і оновлюючи власну таблицю маршрутизації. Замість одного вузла, який знає весь граф, алгоритм виконується паралельно на всіх вузлах мережі одночасно.
Задачі з обмеженнями на кількість кроків. Якщо зупинити алгоритм після k ітерацій, отримаємо найкоротші шляхи з не більш ніж k ребрами. Практичний приклад — задача «знайти найдешевший переліт з не більш ніж двома пересадками».
Bellman-Ford vs Dijkstra
Dijkstra | Bellman-Ford | |
Від'ємні ребра | ❌ некоректний результат | ✅ |
Виявлення негативних циклів | ❌ | ✅ |
Часова складність | ✅ O((V+E) log V) | O(V×E) |
Оптимальний для sparse-графів | ✅ | ❌ |
Якщо граф не містить від'ємних ваг — Дейкстра швидший і простіший у реалізації. Алгоритм Беллмана-Форда виправданий тоді, коли від'ємні ваги є або коли потрібна детекція негативних циклів.
***
Беллман-Форд вирішує задачу, з якою Дейкстра принципово не справляється. За це платять вищою складністю, але в задачах з від'ємними вагами це не компроміс, а єдиний коректний шлях.
Детальніше Bellman-Ford і Dijkstra розбираються в модулі Graphs and Trees курсу Algorithms in Practice.