Bellman-Ford: Отрицательные веса и циклы

Цели урока

• Понять, когда Dijkstra не работает
• Реализовать Bellman-Ford
• Обнаруживать отрицательные циклы
• Знать применения: RIP, арбитраж

Предварительные знания

• Алгоритм Дейкстры

• Dijkstra: кратчайший путь

Dijkstra - быстрый, но хрупкий: одно отрицательное ребро ломает его. Bellman-Ford - медленнее, но надёжен как танк и даже находит «бесконечно короткие» пути через отрицательные циклы.

• RIP протокол маршрутизации
• Арбитраж на валютных рынках
• Системы ограничений в планировании
• Анализ зависимостей (make, компиляторы)

Три имени у одного алгоритма

У Bellman-Ford два имени в названии, но реальные права на него имеют как минимум трое. Ричард Беллман опубликовал алгоритм в 1958 году в Quarterly of Applied Mathematics, и тот органично лёг в его работы по динамическому программированию, сам термин Беллман и придумал во время работы в RAND. Лестер Форд-младший описал ту же идею релаксации ещё в 1956 году в отчёте RAND о потоках в сетях, на два года раньше. А Эдвард Ф. Мур, тот самый Мур из истории BFS, опубликовал эквивалентный метод в 1957 году для задач маршрутизации, поэтому алгоритм иногда называют Bellman-Ford-Moore. Общая суть проста и устойчива: релаксируем каждое ребро V-1 раз, и кратчайшие расстояния гарантированно стабилизируются без всякого предположения о неотрицательности весов. Именно этой устойчивости к отрицательным рёбрам не хватает Дейкстре, и именно она позволяет одним дополнительным проходом обнаружить отрицательный цикл. Метод стал основой distance-vector маршрутизации, включая ранний протокол RIP, где его слабость 'count to infinity' породила позднейшие приёмы вроде split horizon.

Идея: релаксация всех рёбер

**Проблема Dijkstra:** жадный выбор фиксирует вершину, но отрицательное ребро может потом улучшить путь.

**Решение Bellman-Ford:** не фиксируем вершины вообще. Просто V-1 раз проходим по ВСЕМ рёбрам и улучшаем расстояния.

**Почему V-1 итераций?**

**Bellman-Ford проще Dijkstra:** нет приоритетной очереди, просто V-1 проход по рёбрам.

Реализация

**O(VE)** - это медленнее Dijkstra. Используйте Bellman-Ford только если есть отрицательные веса.

Обнаружение отрицательного цикла

**Отрицательный цикл** - цикл с отрицательной суммой весов. Путь можно улучшать бесконечно, проходя по циклу.

**Арбитраж валют:** если есть цикл USD→EUR→JPY→USD с product > 1, можно бесконечно наращивать деньги. Логарифм превращает умножение в сложение, и это отрицательный цикл!

Применения

**1. Маршрутизация (RIP протокол):**

**2. Арбитраж валют:**

**3. Система ограничений (difference constraints):**

Bellman-Ford

• V-1 итераций релаксации всех рёбер
• Работает с отрицательными весами
• Обнаруживает отрицательные циклы
• O(VE) - медленнее Dijkstra
• Используйте только когда есть отрицательные веса

Вопросы для размышления

• Релаксация всех рёбер V-1 раз - это та же идея, что DP-переход dp[v] = min(dp[u] + w). Какие ещё знакомые алгоритмы по сути являются 'тупой' релаксацией, выполненной достаточное число раз?
• Почему RIP-протокол страдает от 'count to infinity', хотя Bellman-Ford математически корректен? Что меняется при переходе от централизованного алгоритма к распределённому?
• Арбитраж валют через -log(rate) - где ещё встречается приём 'превратить умножение в сложение через логарифм', и почему он так часто работает?

Связанные темы

Bellman-Ford - основа для других алгоритмов.

• Dijkstra — Быстрее для неотрицательных весов
• Floyd-Warshall — Все пары кратчайших путей
• SPFA — Оптимизация Bellman-Ford

Связанные уроки

• alg-14-dijkstra — Dijkstra - более быстрый, но без отрицательных рёбер
• alg-16-floyd — Floyd-Warshall - all-pairs версия той же задачи
• alg-12-bfs — BFS решает shortest path при unit weights - базис
• alg-21-dp — Bellman-Ford - DP на графе: relaxation = DP transition
• prob-04-bayes — Итеративное уточнение дистанций - как Bayes update
• ds-16-graphs-intro