Алгоритм Беллмана — Форда

В некоторых задачах о кратчайшем пути есть ребра, которые делают путь дешевле: возврат денег, участок под гору, выгодный обменный курс. Алгоритм Дейкстры с ними не справляется. Алгоритм Беллмана — Форда справляется, меняя хитрость на терпение.

Граф с односторонними стрелками, несколькими отрицательными ребрами, найденными на данный момент расстояниями на вершинах и отрицательным циклом, нарисованным красным
Граф с односторонними стрелками, несколькими отрицательными ребрами, найденными на данный момент расстояниями на вершинах и отрицательным циклом, нарисованным красным

Идея

Любой алгоритм поиска кратчайших путей опирается на один ход — релаксацию ребра: если дойти до 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. В финансах отрицательный логарифм обменных курсов превращает прибыльную цепочку обменов валют в отрицательный цикл, который алгоритм Беллмана — Форда может найти.

Ричард Беллман в 1962 году, фотография Альфреда Эйзенштадта. Он опубликовал метод поиска кратчайших путей в 1958 году, после Шимбела, Форда и Мура.
Ричард Беллман в 1962 году, фотография Альфреда Эйзенштадта. Он опубликовал метод поиска кратчайших путей в 1958 году, после Шимбела, Форда и Мура.

Попробуйте сами

Откройте приложение и нажмите Шаг. Каждое ребро одностороннее, и некоторые длины отрицательные. Каждый шаг проверяет одно ребро в фиксированном порядке, а плитки показывают номер прохода и сколько расстояний он изменил. Обычно вскоре проход уже ничего не меняет, и поиск заканчивается раньше. Отметьте Добавить отрицательный цикл и смотрите, как расстояния уменьшаются проход за проходом, пока контрольный проход не найдет цикл и не нарисует его красным.

Часто задаваемые вопросы

Какова временная сложность алгоритма Беллмана — Форда?

O(V · E) для V вершин и E ребер: до V − 1 проходов, каждый из которых проверяет все ребра. С ранней остановкой на практике он часто намного быстрее, а в лучшем случае хватает одного прохода.

Что такое отрицательный цикл?

Цикл, сумма длин ребер которого меньше нуля. Если обходить его снова и снова, путь становится сколь угодно коротким, поэтому кратчайшие расстояния до вершин, достижимых через него, не определены.

Работает ли алгоритм Беллмана — Форда на неориентированных графах?

Только если нет отрицательных ребер: по неориентированному отрицательному ребру можно ходить туда и обратно, а это отрицательный цикл из двух ребер. С неотрицательными ребрами он работает, но алгоритм Дейкстры быстрее.

Что такое SPFA?

Shortest Path Faster Algorithm — версия алгоритма Беллмана — Форда, которая с помощью очереди заново проверяет только ребра из вершин, чье расстояние только что изменилось. Часто она намного быстрее, хотя худший случай у нее тот же.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать алгоритм Беллмана — Форда