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

Алгоритм Беллмана-Форда — это алгоритм на графах, предназначенный для поиска кратчайших путей от одной заданной вершины (источника) до всех остальных вершин взвешенного графа. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда корректно работает с рёбрами, имеющими отрицательный вес, и позволяет обнаруживать наличие в графе циклов отрицательного суммарного веса, достижимых из исходной вершины. Алгоритм назван в честь математиков Ричарда Беллмана и Лестера Форда-младшего, опубликовавших его в 1958 и 1956 годах соответственно.

История

Алгоритм был впервые описан Лестером Фордом-младшим в 1956 году в работе «Network Flow Theory» (Теория потоков в сетях). Независимо от него, в 1958 году Ричард Беллман опубликовал статью «On a Routing Problem» (О задаче маршрутизации), в которой предложил аналогичный метод. Впоследствии алгоритм также был уточнён Эдвардом Муром в 1959 году, поэтому иногда его называют алгоритмом Беллмана-Форда-Мура.

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

Принцип работы

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

Описание шагов

1. Инициализация: Расстояние до исходной вершины устанавливается равным 0, а до всех остальных вершин — бесконечности (или очень большому числу).
2. Основной цикл: Повторяется |V| - 1 раз (где |V| — количество вершин в графе). На каждой итерации выполняется релаксация всех рёбер графа. Если после |V| - 1 итерации можно выполнить ещё одну релаксацию какого-либо ребра, это означает, что в графе существует цикл отрицательного веса, достижимый из исходной вершины.
3. Проверка на отрицательные циклы: Выполняется дополнительная итерация по всем рёбрам. Если удаётся улучшить расстояние до какой-либо вершины, то фиксируется наличие отрицательного цикла, и алгоритм может быть остановлен.

Формальное описание

Пусть граф G = (V, E) с весовой функцией w: E → R (веса могут быть любыми действительными числами). Пусть s — исходная вершина. Алгоритм вычисляет массив dist[v] — минимальное расстояние от s до v.

``` BellmanFord(G, w, s): // Инициализация for each vertex v in V: dist[v] = INFINITY prev[v] = NULL dist[s] = 0

// Основной цикл for i from 1 to |V| - 1: for each edge (u, v) in E: if dist[u] + w(u, v) < dist[v]: dist[v] = dist[u] + w(u, v) prev[v] = u

// Проверка на отрицательные циклы for each edge (u, v) in E: if dist[u] + w(u, v) < dist[v]: return "Граф содержит цикл отрицательного веса, достижимый из s" return dist, prev ```

Сложность

Временная сложность алгоритма составляет O(|V|·|E|), где |V| — количество вершин, а |E| — количество рёбер. Это делает его менее эффективным, чем алгоритм Дейкстры (сложность O(|E|·log|V|) для графов без отрицательных весов), но более универсальным.

Пространственная сложность составляет O(|V|), так как алгоритм хранит только массивы расстояний и предшественников.

Применение

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

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

Маршрутизация в компьютерных сетях

Алгоритм Беллмана-Форда (или его вариант) использовался в протоколе маршрутизации RIP (Routing Information Protocol). Протокол RIP применяется в локальных и глобальных сетях для обмена информацией о маршрутах. В этом контексте алгоритм работает на распределённой основе: каждый маршрутизатор выполняет вычисления для своего набора соседей. Однако из-за медленной сходимости и проблемы «счёта до бесконечности» (count to infinity) RIP постепенно вытесняется более современными протоколами, такими как OSPF (основан на алгоритме Дейкстры) и EIGRP (гибридный протокол).

Экономика и финансы

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

Другие области

• Анализ транспортных сетей: поиск оптимальных путей с учётом штрафов и бонусов, которые могут быть выражены отрицательными весами.
• Теория игр: в некоторых задачах, например, в играх с графами состояний, где переходы могут иметь как положительные, так и отрицательные выигрыши.
• Линейное программирование: алгоритм может быть использован для решения систем разностных ограничений (систем неравенств вида x_j - x_i ≤ c), которые сводятся к задаче поиска кратчайших путей в графе с возможными отрицательными весами.

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

Интересные факты

• Алгоритм Беллмана-Форда является одним из немногих алгоритмов на графах, который гарантированно находит кратчайшие пути в графах с отрицательными весами, если нет отрицательных циклов.
• В 1994 году Дэвид Эппштейн предложил модификацию алгоритма, которая позволяет находить кратчайшие пути в графах с отрицательными весами за время O(|V|·|E|) без дополнительной проверки на циклы, если граф не содержит циклов отрицательного веса.
• Алгоритм лёг в основу многих задач олимпиадного программирования, где требуется не только найти кратчайший путь, но и проверить граф на наличие отрицательных циклов.

Источники

• Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
• Ford, L. R. (1956). Network Flow Theory. RAND Corporation, Paper P-923.
• Moore, E. F. (1959). The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching, 285-292.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). М.: Вильямс. — Глава 24.5.
• Седжвик, Р. (2014). Алгоритмы на Java (4-е изд.). М.: Вильямс. — Глава 4.4.