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

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

¶История

Алгоритм впервые был опубликован Ричардом Беллманом в 1958 году в статье «On a routing problem» в журнале Quarterly of Applied Mathematics. Лестер Форд-младший также описал его в 1956 году в неопубликованной технической записке корпорации RAND. Впоследствии алгоритм получил широкое распространение в теории графов и сетевых протоколах маршрутизации, таких как протокол RIP (Routing Information Protocol), использующий его модификацию — алгоритм Беллмана — Форда с вектором расстояний (distance vector routing).

¶Описание алгоритма

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

¶Основные шаги

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

¶Псевдокод

``` function BellmanFord(граф G, вершина source): // Инициализация distance[source] = 0 for each vertex v in G: if v != source: distance[v] = INFINITY predecessor[v] = NULL

// Релаксация рёбер |V|-1 раз for i = 1 to |V|-1: for each edge (u, v) with weight w in G: if distance[u] + w < distance[v]: distance[v] = distance[u] + w predecessor[v] = u

// Проверка на отрицательные циклы for each edge (u, v) with weight w in G: if distance[u] + w < distance[v]: error "Граф содержит отрицательный цикл" ```

¶Сложность

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

¶Применение

¶1. Сетевые протоколы маршрутизации

Алгоритм Беллмана — Форда лежит в основе протоколов маршрутизации, основанных на векторе расстояний, таких как RIP (Routing Information Protocol). В этих протоколах каждый маршрутизатор хранит таблицу расстояний до всех известных сетей и периодически обменивается ею с соседями. Алгоритм позволяет динамически обновлять маршруты при изменении топологии сети, хотя он подвержен проблеме «счёта до бесконечности» (count-to-infinity), которая решается введением механизмов, таких как «разделение горизонта» (split horizon) и «принудительное обновление» (route poisoning).

¶2. Поиск кратчайших путей в графах с отрицательными весами

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

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

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

¶4. Задачи линейного программирования

Алгоритм может использоваться для решения систем разностных ограничений (difference constraints), которые сводятся к задаче поиска кратчайших путей в графе с рёбрами, соответствующими неравенствам вида x_j − x_i ≤ c. Этот подход применяется в задачах планирования, синтеза расписаний и верификации программ.

¶Модификации и улучшения

¶Алгоритм SPFA (Shortest Path Faster Algorithm)

Является оптимизацией алгоритма Беллмана — Форда, использующей очередь для хранения вершин, которые нужно обработать. В среднем SPFA работает быстрее, чем классический алгоритм, но его временная сложность в худшем случае остаётся O(|V| × |E|). Алгоритм SPFA широко применяется в китайской олимпиадной практике по программированию.

¶Алгоритм с ранним завершением

Если в процессе релаксации на некоторой итерации (от 1 до |V|−1) не было произведено ни одного обновления расстояний, алгоритм можно завершить досрочно, так как дальнейшие итерации не изменят результат. Это улучшает среднюю производительность на графах, где кратчайшие пути находятся быстро.

¶Алгоритм Йена

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

¶Пример работы

Рассмотрим ориентированный граф с вершинами A, B, C, D и рёбрами:

• A → B (вес 4)
• A → C (вес 2)
• B → C (вес -3)
• B → D (вес 2)
• C → D (вес 1)

Пусть исходная вершина — A. Начальные расстояния: dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞.

Итерация 1:

• Ребро A→B: dist[B] = 0 + 4 = 4
• Ребро A→C: dist[C] = 0 + 2 = 2
• Ребро B→C: dist[C] = min(2, 4 + (-3) = 1) → обновляется до 1
• Ребро B→D: dist[D] = 4 + 2 = 6
• Ребро C→D: dist[D] = min(6, 1 + 1 = 2) → обновляется до 2

Итерация 2:

• Ребро A→B: dist[B] = 4 (не меняется)
• Ребро A→C: dist[C] = 1 (не меняется)
• Ребро B→C: dist[C] = min(1, 4 + (-3) = 1) → не меняется
• Ребро B→D: dist[D] = min(2, 4 + 2 = 6) → не меняется
• Ребро C→D: dist[D] = min(2, 1 + 1 = 2) → не меняется

Итерация 3 (|V|−1 = 3, но на 2-й итерации не было изменений, алгоритм мог бы завершиться раньше):

• Ни одно ребро не приводит к улучшению.

Проверка на отрицательные циклы:

• Ни одно ребро не релаксируется, следовательно, отрицательных циклов нет.

Кратчайшие расстояния от A: до B — 4, до C — 1, до D — 2. Кратчайшие пути: A→C→D (вес 2) и A→B→C (вес 1).

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

• Алгоритм Беллмана — Форда является одним из первых алгоритмов, способных работать с отрицательными весами, и до сих пор остаётся стандартным методом для этой задачи.
• В 2003 году алгоритм был включён в список 50 наиболее влиятельных алгоритмов в области компьютерных наук по версии журнала Computing in Science & Engineering.
• Название алгоритма часто пишется как «Беллмана — Форда» (с тире), хотя в англоязычной литературе используется «Bellman–Ford algorithm».
• Алгоритм не требует, чтобы граф был связным; он корректно обрабатывает вершины, недостижимые из источника, оставляя их расстояние бесконечным.

¶Источники

• 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.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.