Информатика / Алгоритмы и анализ данных

Алгоритм Беллмана — Форда: путь с отрицательными весами

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

Опубликовано: 20 октября 2026 г.Обновлено: 20 октября 2026 г.

Формула

d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)

Схема Беллман — Форд: три прохода

На схеме буквенные узлы показаны по порядку пути

Обозначения

$d_k(v)$: лучшая стоимость пути от s до v не более чем из k рёбер, единица веса
$w(u,v)$: вес дуги u → v, единица веса
$E$: множество дуг, множество
$k$: предельное число рёбер в пути, количество
$s$: источник с d₀(s) = 0, идентификатор

Условия применения

В показанной рекурсии все новые метки вычисляют из предыдущего слоя. Инициализация: d₀(s) = 0, прочие бесконечны. Для конечного кратчайшего маршрута к цели не должно быть отрицательного цикла, достижимого из старта и способного затем привести к этой цели.

Ограничения

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

Подробное объяснение

Рекурсия разделяет пути по числу рёбер. Путь до v либо уже найден на предыдущем слое, либо заканчивается некоторой дугой u→v. В последнем случае к пути до u добавляется её вес. Минимум по всем таким вариантам даёт лучший маршрут не более чем с k рёбрами.

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

Дополнительный проход имеет диагностический смысл. Если метка всё ещё улучшается из достижимой вершины, обычного простого пути уже недостаточно: присутствует отрицательный цикл, до которого можно добраться из источника. Это не просто «медленная сходимость», и продолжать выдавать уменьшающуюся метку как минимум нельзя.

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

Классический полный обход требует O(VE) времени. Можно завершить раньше, если целый проход не изменил ни одной метки. Для конкретной цели после обнаружения цикла важно проверить, достижима ли она из цикла: наличие отрицательного цикла где-то в сети не отменяет все остальные конечные расстояния.

Как пользоваться формулой

Инициализируйте слой ноль и перечислите все ориентированные рёбра со знаками весов; отдельно задайте представление бесконечности.
Для каждого нового слоя скопируйте старые расстояния и релаксируйте дуги только из конечных меток предыдущего слоя.
Выполните до V−1 проходов; при отсутствии изменений завершите раньше, сохраняя предшественников для конечных путей.
Проверьте ещё один проход на улучшения и отделите вершины под влиянием достижимого отрицательного цикла от конечных расстояний.

Историческая справка

Работы по сетевым маршрутам середины XX века связывают метод с Ричардом Беллманом и Лестером Фордом. Публикация Беллмана On a routing problem 1958 года рассматривает оптимальный маршрут через функциональные уравнения динамического программирования. Работа Форда Network Flow Theory относится к 1956 году и представлена в каталоге RAND. Современное двойное название отражает развитие сетевых методов несколькими исследователями, а не единственную строку кода. В учебной записи через число рёбер особенно хорошо виден принцип оптимальности: лучшая последняя дуга соединяется с уже лучшим допустимым префиксом. Практическая реализация добавляет проверку отрицательных циклов, защиту от переполнения и хранение маршрута. Эти детали следует отличать от исходной постановки транспортной задачи.

Историческая линия формулы

Используется принятое имя Беллмана — Форда. Указаны работа Беллмана 1958 года и материал Форда 1956 года как исторические источники сетевой постановки. Формула слоёв и современная программная реализация приведены в учебном виде без заявления об исключительном первенстве.

Пример

Пусть есть дуги S→A весом 4, S→B весом 5, A→B весом −2 и B→T весом 3. Все веса заданы в условных единицах. На слое ноль конечен только S = 0. После первого слоя A = 4, B = 5, T = ∞. На втором B улучшается до 4−2 = 2, а T получает 5+3 = 8 из старого значения B. На третьем T уменьшается до 2+3 = 5. Получен путь S→A→B→T стоимости 4−2+3 = 5. Четвёртый проход ничего не меняет. В этом графе четыре вершины, так что три прохода соответствуют границе V−1. Прямая ветка через B стоит 5+3 = 8. Отрицательное ребро допустимо и не образует отрицательного цикла: обратных дуг здесь вообще нет.

Частая ошибка

Не отвергайте любое отрицательное ребро как цикл: это разные свойства. Не переносите смысл «не более k рёбер» на обновление массива на месте без оговорки. Не релаксируйте из бесконечной метки. Не выдавайте расстояние до вершины под влиянием отрицательного цикла как конечный минимум. Не считайте недостижимый цикл обнаруженным из данного старта.

Практика

Задачи с решением

Отрицательный цикл

Условие. Есть S→A весом 1, A→B весом −3 и B→A весом 1. Что происходит с расстояниями до A и B?

Решение. Цикл A→B→A имеет вес −3+1 = −2 и достижим из S. Каждый новый оборот уменьшает стоимость ещё на 2. Конечного минимума для A и B нет.

Ответ. Обе стоимости неограничены снизу.

Цикл вне досягаемости

Условие. Есть S→T весом 7 и отдельные A→B весом −3, B→A весом 1; других дуг нет. Найдите S→T.

Решение. Из S доступны лишь S и T. Метки A,B бесконечны и не релаксируют друг друга. Отдельный отрицательный цикл не влияет на T.

Ответ. Кратчайшая стоимость S→T равна 7.

Дополнительные источники

https://algs4.cs.princeton.edu/44sp/index.php
https://www.cs.yale.edu/homes/lans/readings/routing/bellman-routing-1958.pdf
https://www.rand.org/pubs/papers/P923.html

Связанные формулы

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

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

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

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

Информатика

Алгоритм Флойда — Уоршелла: пути между всеми парами

$d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)$

Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.