Алгоритм Беллмана-Форда: как найти кратчайшие пути в графах с отрицательными весами

hannadev

Алгоритм Беллмана-Форда помогает находить кратчайшие пути от одной вершины графа до всех остальных. Он уникален тем, что работает даже с отрицательными весами рёбер, в отличие от алгоритма Дейкстры. Это решает проблему, когда в графе есть минусы, и стандартные методы дают сбой.

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

Как устроен алгоритм Беллмана-Форда

Алгоритм основан на релаксации рёбер: мы многократно проходим по всем рёбрам графа и пытаемся улучшить расстояния. Начинаем с расстояния 0 до стартовой вершины и бесконечности до остальных. Каждая итерация учитывает пути длиной на одно ребро больше предыдущей.

После (|V| - 1) итераций, где |V| — число вершин, мы получаем кратчайшие пути, если отрицательных циклов нет. Дополнительный проход проверяет наличие таких циклов: если расстояния ещё обновляются, цикл существует. Это простой, но мощный подход динамического программирования.

Инициализация: distance[s] = 0, остальные = ∞, predecessor = null.
Релаксация: для каждого ребра (u, v) if distance[v] > distance[u] + w(u,v), обновляем distance[v] и predecessor[v] = u.
Повтор: |V|-1 раз по всем рёбрам.
Проверка цикла: ещё один проход; если обновления есть — отрицательный цикл.

Вот пример графа с 4 вершинами (0,1,2,3) и рёбрами: (0,1:5), (0,2:2), (1,3:3), (2,3:1), (2,1:-2).

Итерация	distance	distance	distance
Начало	∞	∞	∞
1	5	2	∞
2	0	2	3
3	0	2	3

Обратите внимание: на второй итерации ребро (2,1:-2) улучшает путь до 1 через 2.

Сравнение с другими алгоритмами поиска путей

Алгоритм Беллмана-Форда универсален, но не самый быстрый: сложность O(VE), где V — вершины, E — рёбра. Дейкстра быстрее O((V+E)logV), но не берёт отрицательные веса. Если граф большой и веса положительные, лучше взять Дейкстру или A*.

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

Алгоритм	Отрицательные веса	Сложность	Обнаруживает циклы
Дейкстра	Нет	O((V+E)logV)	Нет
Беллман-Форд	Да	O(VE)	Да
Флойд-Воршелл	Да	O(V³)	Да

Ключевой плюс: работает с минусами без топологической сортировки. Минус: медленно на плотных графах.

Реализация на Python: код и пример

Реализовать просто: массив расстояний, список рёбер, цикл релаксаций. Используем INF = 10**9 для бесконечности. Код универсален для любых графов.

Вот базовая функция:

INF = 10**9

def bellman_ford(graph, start, n):
    distance = [INF] * n
    distance[start] = 0
    predecessor = [None] * n
    
    for _ in range(n - 1):
        for u, v, w in graph:
            if distance[u] != INF and distance[v] > distance[u] + w:
                distance[v] = distance[u] + w
                predecessor[v] = u
    
    # Проверка отрицательного цикла
    for u, v, w in graph:
        if distance[u] != INF and distance[v] > distance[u] + w:
            return None, "Отрицательный цикл"
    
    return distance, predecessor

Пример графа: graph = [(0,1,5), (0,2,2), (1,3,3), (2,3,1), (2,1,-2)]. Вызов bellman_ford(graph, 0, 4) даст [0, 0, 2, 3].

Восстановление пути: от цели идём по predecessor назад до start.
Оптимизация: пропускайте вершины с distance=INF.
Для неориентированных: дублируйте рёбра в обе стороны.

В распределённых системах добавьте обмен сообщениями между узлами.

Оптимизации и типичные ошибки в практике

Базовый алгоритм медленный, но можно ускорить: используйте очередь активных вершин, как в SPFA (Shortest Path Faster Algorithm) — сложность ближе к O(E). Ещё вариант: ранний стоп, если итерация не обновила ничего.

Частые ошибки: забывка проверки цикла приводит к неверным путям; неинициализированные predecessor рвут восстановление пути. Тестируйте на графах с циклами и недостижимыми вершинами.

SPFA: очередь для релаксации изменённых вершин.
Ранний выход: if no updates — break.
Хранение графа: список рёбер удобен, но adjacency list быстрее для sparse.

В реальных проектах: комбинируйте с Дейкстрой — сначала проверьте положительные ли веса.

Когда отрицательный цикл меняет всё

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

В задачах это сигнал: либо исключить цикл, либо сообщить “невозможно”. В сетях — признак арбитража. Подумайте, как обработать такие случаи в вашем коде: вернуть None или специальное значение.

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