Що робить алгоритм Беллмана-Форда?

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

---

#Ідея

Він багаторазово «розслаблює» (оновлює) всі ребра графа, поки відстані до всіх вершин не стабілізуються.

«Розслабити ребро» (u → v) з вагою w означає: якщо через u можна потрапити в v дешевше, ніж раніше, то оновлюємо: [ dist[v] = dist[u] + w ]

---

#Як це працює

1. Задати відстань до всіх вершин = ∞, крім стартової (0).
2. Повторити |V| - 1 раз (де |V| - число вершин):

• Для кожного ребра (u, v, w): якщо dist[u] + w < dist[v], оновити dist[v].

3. Після цього зробити ще один прохід:

• Якщо на якомусь ребрі відстань усе ще можна зменшити, значить, є від'ємний цикл (шлях, що зменшує відстань нескінченно).

---

#Приклад

Нехай ребра: A → B (4), A → C (5), B → C (-3)

1. Старт: dist[A]=0, dist[B]=∞, dist[C]=∞
2. Після 1-ї ітерації:

• dist[B] = 4
• dist[C] = 5

3. Розслаблюємо B→C: dist[C] = 4 + (-3) = 1 → найкоротший шлях A → B → C = 1

---

#Складність

• Час: O(V × E)
• Пам'ять: O(V)

---

#Переваги

• Працює з від'ємними вагами.
• Може виявити від'ємні цикли.

#Недоліки

• Повільніший, ніж алгоритм Дейкстри.

---

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