Алгоритм Беллмана — Форда
В некоторых задачах о кратчайшем пути есть ребра, которые делают путь дешевле: возврат денег, участок под гору, выгодный обменный курс. Алгоритм Дейкстры с ними не справляется. Алгоритм Беллмана — Форда справляется, меняя хитрость на терпение.
Идея
Любой алгоритм поиска кратчайших путей опирается на один ход — релаксацию ребра: если дойти до u, а затем пройти по ребру u → v короче, чем лучший известный путь до v, используйте этот путь. Алгоритм Дейкстры релаксирует каждое ребро один раз, в хитром порядке, который работает, только если отрицательных ребер нет. Алгоритм Беллмана — Форда ничего такого не предполагает. Он релаксирует каждое ребро, в любом фиксированном порядке, снова и снова, пока расстояния не перестанут меняться.
По шагам
Дайте старту расстояние 0, а всем остальным вершинам — бесконечность. Повторите n − 1 раз для n вершин: пройдите по каждому ребру u → v и релаксируйте его, если у u есть расстояние. Остановитесь раньше, если целый проход ничего не меняет. Затем сделайте еще один проход. Если какое-то ребро все еще можно релаксировать, из старта достижим цикл с отрицательной суммой; иначе каждое расстояние кратчайшее, а запомненные вершины дают пути.
Пример
Возьмите односторонние ребра A → B длиной 4, A → C 5, B → D 2 и C → B −3, которые проверяются в этом порядке, начиная с A. Проход 1 дает B 4, C 5 и D 6, а затем C → B уменьшает B до 5 − 3 = 2. Проход 2 уменьшает D до 2 + 2 = 4. Проход 3 ничего не меняет, поэтому ответ: B 2, C 5, D 4. Алгоритм Дейкстры сделал бы B окончательной с 4, а D — с 6, еще до того, как увидел отрицательное ребро. Добавьте ребро D → C длиной −4, и сумма цикла C → B → D → C станет −5: каждый проход снова уменьшает расстояния, и контрольный проход сообщает об этом.
Почему хватает n − 1 проходов
Кратчайший путь, если он существует, никогда не повторяет вершину, поэтому в нем не больше n − 1 ребер. Релаксация всех ребер за проход удлиняет каждый правильно известный кратчайший путь еще на одно ребро, каким бы ни был порядок ребер. Значит, после прохода k все кратчайшие пути не больше чем из k ребер верны, а после n − 1 проходов — все. Порядок все же влияет на скорость: при удачном порядке хватает одного-двух проходов.
История и применения
Альфонсо Шимбел описал метод в 1955 году, Лестер Форд-младший — в 1956-м, Эдвард Ф. Мур — в 1957-м, а Ричард Беллман — в 1958 году; метод носит имена двоих из них, Беллмана и Форда. Его проходы может выполнять каждый маршрутизатор сам по себе, поэтому он стал основой дистанционно-векторных протоколов маршрутизации, таких как RIP. В финансах отрицательный логарифм обменных курсов превращает прибыльную цепочку обменов валют в отрицательный цикл, который алгоритм Беллмана — Форда может найти.
Попробуйте сами
Откройте приложение и нажмите Шаг. Каждое ребро одностороннее, и некоторые длины отрицательные. Каждый шаг проверяет одно ребро в фиксированном порядке, а плитки показывают номер прохода и сколько расстояний он изменил. Обычно вскоре проход уже ничего не меняет, и поиск заканчивается раньше. Отметьте Добавить отрицательный цикл и смотрите, как расстояния уменьшаются проход за проходом, пока контрольный проход не найдет цикл и не нарисует его красным.
Часто задаваемые вопросы
Какова временная сложность алгоритма Беллмана — Форда?
O(V · E) для V вершин и E ребер: до V − 1 проходов, каждый из которых проверяет все ребра. С ранней остановкой на практике он часто намного быстрее, а в лучшем случае хватает одного прохода.
Что такое отрицательный цикл?
Цикл, сумма длин ребер которого меньше нуля. Если обходить его снова и снова, путь становится сколь угодно коротким, поэтому кратчайшие расстояния до вершин, достижимых через него, не определены.
Работает ли алгоритм Беллмана — Форда на неориентированных графах?
Только если нет отрицательных ребер: по неориентированному отрицательному ребру можно ходить туда и обратно, а это отрицательный цикл из двух ребер. С неотрицательными ребрами он работает, но алгоритм Дейкстры быстрее.
Что такое SPFA?
Shortest Path Faster Algorithm — версия алгоритма Беллмана — Форда, которая с помощью очереди заново проверяет только ребра из вершин, чье расстояние только что изменилось. Часто она намного быстрее, хотя худший случай у нее тот же.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать алгоритм Беллмана — Форда