Проход
Изменено за проход
Проверенные ребра

  • Текущая
  • Есть расстояние
  • Использованное ребро
  • Путь
  • Отрицательный цикл
Щелчок по вершине задает

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

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

Алгоритм Дейкстры ломается, когда у ребра отрицательная длина, — как у дороги, которая не берет с вас плату за проезд, а сама платит вам. Алгоритм Беллмана — Форда не ломается: он просто проверяет каждое ребро снова и снова, пока ничего не улучшается, и даже замечает, когда из-за цикла расстояния уменьшаются бесконечно. Щелкните вершину, чтобы начать с нее, и пройдите проходы по шагам. Нажмите Пуск, чтобы следить за поиском, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Каждое ребро одностороннее, как показывает стрелка, а число на нем — его длина, которая может быть отрицательной. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы в конце увидеть кратчайший путь до нее. Число на каждой вершине — ее расстояние на данный момент. Отметьте Добавить отрицательный цикл, чтобы увидеть, как алгоритм Беллмана — Форда его находит. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом. Чтобы в конце увидеть путь, переключите щелчок на Цель и щелкните другую вершину.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
  3. Отметьте Добавить отрицательный цикл, чтобы увидеть, как алгоритм Беллмана — Форда его находит. Кнопка Новый граф создает другой граф для пробы.

Как работает алгоритм Беллмана — Форда

Дайте старту расстояние 0, а всем остальным вершинам — бесконечность. Затем делайте проходы: в каждом проходе проверьте один раз каждое ребро u → v. Если у u есть расстояние и dist(u) плюс длина ребра меньше dist(v), уменьшите dist(v) и запомните u как путь туда. После прохода k известен каждый кратчайший путь не больше чем из k ребер. Кратчайший путь проходит через каждую вершину не больше одного раза, поэтому в нем не больше n − 1 ребер, и n − 1 проходов всегда хватает. Если целый проход ничего не меняет, поиск можно закончить раньше.

Поиск отрицательного цикла

Если сумма ребер цикла меньше нуля, еще один круг по нему всегда делает путь короче, поэтому кратчайшего пути нет вовсе. Алгоритм Беллмана — Форда это замечает: после n − 1 проходов еще один проход не должен ничего менять. Если какое-то ребро все еще можно релаксировать, из старта достижим отрицательный цикл, и если идти назад по запомненным вершинам от этого ребра, попадешь в него. В приложении цикл рисуется красным.

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

Что такое алгоритм Беллмана — Форда?

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

Почему алгоритм Дейкстры не работает с отрицательными ребрами?

Дейкстра делает расстояние вершины окончательным, как только она оказывается ближайшей в очереди. Отрицательное ребро, найденное позже, может привести обратно к этой вершине более коротким путем, и тогда окончательное расстояние окажется неверным. Алгоритм Беллмана — Форда никогда не делает расстояние окончательным раньше времени; он продолжает проверять каждое ребро.

Почему n − 1 проходов?

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

Насколько быстр алгоритм Беллмана — Форда?

Каждый проход проверяет все E ребер, а проходов не больше V − 1, поэтому работа растет как V × E. Это медленнее алгоритма Дейкстры, поэтому алгоритм Беллмана — Форда используют, когда ребра могут быть отрицательными.

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

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

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

Перейти в редактор