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

Алгоритм Беллмана–Форда (BF) решает классическую задачу поиска кратчайших путей от одной исходной вершины в ориентированном (или неориентированном) взвешенном графе с возможными отрицательными весами рёбер. В отличие от жадного алгоритма Дейкстры, BF корректно работает при наличии отрицательных весов и позволяет обнаруживать достижимые отрицательные циклы (циклы с суммарным весом < 0), в присутствии которых кратчайшие пути не определены.

Для ЕГЭ эта тема важна, потому что:

• тренирует работу с таблицами рёбер и итеративными обновлениями (релаксация);

• требует аккуратности в инвариантах и границах количества итераций;

• помогает уверенно отличать корректные постановки (без отрицательных циклов) от некорректных.

Формальная постановка и модель данных

Релаксация и инвариант алгоритма

Классический алгоритм (пошаговая спецификация)

Корректность и границы

1. Почему n−1n-1n−1 проходов достаточно?
   Любой простой путь в графе имеет ≤ n−1 рёбер. На k-м проходе становятся корректными расстояния для путей длиной до k. Значит, после n−1 проходов все кратчайшие расстояния (если они определены) уже найдены.
   

2. Обнаружение отрицательных циклов
   
   

Где Беллман–Форд уместен, а где нет

• Использовать BF, если:

• в графе есть отрицательные веса;

• требуется детектировать отрицательные циклы;

• граф умеренного размера, либо нужно гарантированное поведение без ограничений на веса.

• Лучше Дейкстры, если: все веса неотрицательны и важна скорость (обычно O((n+m)logn).

• Лучше Флойда–Уоршелла, если: нужно расстояние между всеми парами вершин (стоимость O(n3)).

• Особый случай – DAG: если граф ацикличен (ориентированный ацикличный), то кратчайшие пути считаются за O(n+m) после топологической сортировки (динамическое программирование по порядку).

Важное замечание про неориентированные графы с отрицательными весами. Любое отрицательное ребро {u,v} мгновенно даёт цикл u→v→u весом 2⋅w(u,v)<0. Значит, кратчайшие пути не определены. Поэтому практический интерес BF – именно ориентированные графы (или неориентированные без отрицательных рёбер).

Практические правила (инженерные детали)

1. Порядок рёбер. На корректность не влияет; на удобство трассировки – влияет (для ЕГЭ удобно упорядочить таблицу рёбер по возрастанию).

2. Досрочный выход. Если в проходе нет улучшений, дальнейшие проходы бессмысленны – используйте флаг изменений.

3. Восстановление циклов. При обнаружении улучшения на шаге проверки: стартуйте от вершины v, пройдите n раз по predpredpred, чтобы гарантированно попасть внутрь цикла, затем обходите до повторения вершины.

4. Типы данных. При больших абсолютных весах используйте типы с запасом (64-битные целые, фиксируйте поведение при переполнении).

5. Формат входа на ЕГЭ. Часто граф задан списком рёбер в таблице – это идеально для BF: просто «крутите» таблицу как есть.

Вариации и оптимизации

1. Раннее завершение

Добавляйте логический флаг changed. Если за проход ни одна релаксация не сработала, break. Это сохраняет асимптотику, но ускоряет типичные случаи.

2. Очередная релаксация (SPFA-подход)

Идея: хранить в очереди только те вершины, чьи расстояния только что улучшились, и релаксировать исходящие рёбра именно из них. В среднем часто быстрее, но в худшем случае тоже O(n⋅m) (и может работать медленно на специально сконструированных графах). В рамках ЕГЭ достаточно знать классический BF.

3. Явное восстановление отрицательного цикла

Если при проверке улучшилось ребро (u,v), возьмите x←vx и выполните n раз x←pred[x]. Теперь x гарантированно на цикле. Идите от x по pred до повторного попадания в x, фиксируя вершины – это и есть цикл с отрицательной суммой весов.

Типичные ошибки

• Игнорирование замечания о неориентированном графе с отрицательным ребром (там кратчайшие пути не определены).

• Неправильная интерпретация числа проходов (делают n вместо n−1 и путают с фазой проверки).

• Переполнение целых типов при больших весах и суммах.

Связь с подготовкой к ЕГЭ

• Формат заданий. Часто дан список рёбер с весами и требуется:

1. выполнить несколько итераций релаксации и заполнить таблицу distdistdist;

2. определить наличие отрицательного цикла;

3. восстановить путь и вычислить его вес.

• Навыки. Внимательное пошаговое обновление, работа с «бесконечностью», аккуратное восстановление, доказательная логика («почему достаточно n−1 проходов»).

• Проверка решений. После завершения сравнивайте значения dist[v] с прямыми вычислениями на малых примерах; убедитесь, что улучшения на шаге проверки отсутствуют.

Мини-пример (ручная трассировка)

Пять упражнений (академический формат «теория + практика»)

Упражнение 1. Таблица релаксаций и ранний выход

Упражнение 2. Контрпример к Дейкстре и корректность BF

Постройте небольшой ориентированный граф, где есть отрицательное ребро, нет отрицательных циклов, и Дейкстра даёт неверный ответ, а BF – корректный.
a) Укажите исходную вершину, таблицу рёбер и правильные кратчайшие расстояния.
b) Поясните, на каком шаге Дейкстра ошибается (жадная фиксация), и почему BF не подвержен этой ошибке.
c) Проверьте, что на последнем шаге BF отсутствуют улучшения – значит, отрицательных циклов нет.

Упражнение 3. Неориентированный граф с отрицательным ребром

Упражнение 4. Восстановление отрицательного цикла

Дан ориентированный граф и результат работы BF: на проверочной фазе обнаружено улучшение по ребру (u,v). Известен массив pred.
a) Опишите точный алгоритм восстановления отрицательного цикла через проход n раз по pred и последующее обходное замыкание.
b) Обоснуйте, почему проход именно n раз гарантирует попадание внутрь цикла.
c) Укажите, как вычислить суммарный вес найденного цикла и проверить его отрицательность.

Упражнение 5. DAG и ускорение относительно BF

Дан ориентированный ацикличный граф в виде списка рёбер.
a) Предложите алгоритм поиска кратчайших путей от s быстрее, чем O(n⋅m), и укажите его сложность.
b) Объясните, почему в DAG нет смысла выполнять n−1 проходов BF.
c) Проведите аналогию между «релаксацией по топологическому порядку» и динамическим программированием.

Заключение

Алгоритм Беллмана–Форда – базовый инструмент работы с кратчайшими путями при отрицательных весах и для детекции отрицательных циклов. Его теоретическая опора – инвариант длины пути по числу рёбер и строгий предел в n−1 проходов. На практике важно аккуратно реализовать релаксацию, проверку достижимости и фазу обнаружения циклов, уметь восстанавливать пути и циклы, корректно выбирать типы данных. Для ЕГЭ владение BF означает уверенную работу с таблицами рёбер, поэтапными обновлениями и корректными выводами о существовании/несуществовании кратчайших путей – навыки, которые напрямую конвертируются в высокие баллы.