Беллман-Форд: Найкоротші Шляхи, Коли Деякі Ребра Віднімають Замість Додавання

Алгоритм Дейкстри має обмеження

Алгоритм Дейкстри ефективно знаходить найкоротші шляхи, але він припускає, що всі ваги ребер невід’ємні. Він жадібно обирає найближчий непроглянутий вузол, вважаючи, що пізніше відкриття ніколи не може зробити вже завершений шлях коротшим. Негативна вага ребра порушує це припущення: шлях, який спочатку здавався довгим, все ще може виявитися коротшим, коли він отримає негативну вагу ребра пізніше. Алгоритм Беллмана-Форда, розроблений незалежно Річардом Беллманом і Лестером Фордом у 1950-х роках, правильно обробляє від’ємні ваги, відмовившись від жадібного кроку Дейкстри та замість цього повторно розслабляючи всі ребра графа.

Повторне розслаблення (V-1 разів)

Розслаблення ребра (u, v) з вагою w означає: якщо найкрадіючий відомий шлях до u, плюс w, менший за найкращий відомий шлях до v, оновіть відстань до v таким кращим значенням. Весь алгоритм Беллмана-Форда складається з: ініціалізації відстані джерела до 0 та всього іншого до нескінченності, потім розслаблення кожного ребра у графі, та повторення цього повного проходу V-1 разів, де V - кількість вершин.

dist[джерело] = 0; dist[всі інші] = Нескінченність повторити (V - 1) разів: для кожного ребра (u, v, w) у графі: якщо dist[u] + w < dist[v]: dist[v] = dist[u] + w // ще один прохід для перевірки на негативні цикли: для кожного ребра (u, v, w): якщо dist[u] + w < dist[v]: повідомлення "досягнуто негативний цикл з джерела" Чому V-1 проходів точно? Найкоротший шлях між будь-якими двома вершинами, якщо він існує та граф не містить негативних циклів, відвідує щонайбільше V-1 ребер (шлях, який відвідує більше ніж це число, повинен повторювати вершину, що означає, що він містить цикл, а видалення цього циклу може скоротити шлях у графі без негативних циклів, роблячи його вигідним для збереження). Кожен повний прохід по всіх ребрах гарантовано правильно розширює принаймні один найкоротший шлях на одне додаткове ребро, в найгіршому випадку поширюючи корекцію на один крок далі вниз за найдовшим можливим найкоротшим шляхом на кожному проході — тому V-1 проходів достатньо для гарантування того, що будь-який найкоротший шлях, незалежно від кількості ребер, необхідних для його побудови, повністю розслаблений.

dist[source] = 0;  dist[all others] = Infinity
repeat (V - 1) times:
  for each edge (u, v, w) in the graph:
    if dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
// one more pass to check for negative cycles:
for each edge (u, v, w):
  if dist[u] + w < dist[v]:  report "negative cycle reachable from source"

Бонус: виявлення негативних циклів безкоштовно

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

Вартість загальності: O(V·E) замість O(E log V)

Алгоритм Беллмана-Форда з бінарним або фібоночим кущами працює приблизно за час O(E log V) або краще; повний перегляд усіх E ребер алгоритмом Беллмана-Форда, що складається з V-1 проходів, коштує O(V*E), значно повільніше на великих, щільних графах. У практиці цей компроміс виправданий лише тоді, коли негативні ваги дійсно потрібні, або коли алгоритму Беллмана-Форда важлива інша властивість: оскільки це простий, уніфікований цикл з розслабленням кожного краю без черги пріоритетів, він більш природно паралелізується та розподіляється, ніж нав'язливий жадібний вибір алгоритму Дейкстри, що є точно тому, чому протоколи маршрутизації на основі векторів відстаней, такі як оригінальний RIP-протокол, використовують розповсюджену варіацію алгоритму Беллмана-Форда, де кожен маршрутизатор повинен знати лише оцінки відстаней від своїх безпосередніх сусідів, а не всю топологію мережі.

Звідки беруться від’ємні ваги на практиці

Від’ємні ваги ребер не є просто теоретичним явищем: вони з'являються, коли ребро представляє собою чисту вигоду, а не лише витрату. Це стосується виявлення арбітражів у графах валютних операцій, де логарифм курсу обміну може бути від’ємним, або коли від’ємний цикл буквально вказує на прибутковий арбітражний ланцюг, а також у формулюваннях графів обмежень для задач планування, де вага ребра може кодувати необхідний часовий інтервал, який дозволено зробити від’ємним. Виявлення від’ємних циклів алгоритмом Bellman-Ford в арбітражному випадку – це не окремий випадок, який потрібно захищати – це фактична відповідь, яку виконує алгоритм.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Bellman-Ford і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.