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

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Беллмана-Форда предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность $O(mn)$ против $O(m + n\ln n)$ у алгоритма Дейкстры), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.

1.2 Математическое описание

Пусть задан граф $G = (V, E)$ с весами рёбер $f(e)$ и выделенной вершиной-источником $u$. Обозначим через $d(v)$ кратчайшее расстояние от источника $u$ до вершины $v$.

Алгоритм Беллмана-Форда ищет функцию $d(v)$ как единственное решение уравнения

$d(v) = \min \{ d(w) + f(e) \mid e = (w, v) \in E \}, \quad \forall v \ne u,$

с начальным условием $d(u) = 0$.

1.3 Вычислительное ядро алгоритма

Основной операцией алгоритма является релаксация ребра: если $e = (w, v) \in E$ и $d(v) \gt d(w) + f(e)$, то производится присваивание $d(v) \leftarrow d(w) + f(e)$.

1.4 Макроструктура алгоритма

Алгоритм последовательно уточняет значения функции $d(v)$.

• В самом начале производится присваивание $d(u) = 0$, $d(v) = \infty$, $\forall v \ne u$.
• Далее происходит $n-1$ итерация, в ходе каждой из которых производится релаксация всех рёбер графа.

1.5 Описание схемы реализации последовательного алгоритма

Последовательный алгоритм реализуется следующим псевдокодом:

Входные данные:
  граф с вершинами V, рёбрами E с весами f(e);
  вершина-источник u.
Выходные данные: расстояния d(v) до каждой вершины v ∈ V от вершины u.

for each v ∈ V do d(v) := ∞
d(u) = 0

for i from 1 to |V| - 1:
    for e = (w, v) ∈ E:
        if d(v) > d(w) + f(e):
            d(v) := d(w) + f(e)

1.8 Описание ресурса параллелизма алгоритма

Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Беллмана-Форда.

1.10 Свойства алгоритма

Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро $e = (v, w)$ лежит на таком цикле, если вычисленные алгоритмом кратчайшие расстояния $d(v)$ удовлетворяют условию

$d(v) + f(e) \lt d(w),$

где $f(e)$ – вес ребра $e$. Условие может быть проверено для всех рёбер графа за время $O(m)$.

2 Программная реализация алгоритмов

2.7 Существующие реализации алгоритма

• C++: Boost Graph Library (функция bellman_ford_shortest).
• Python: NetworkX (функция bellman_ford).
• Java: JGraphT (класс BellmanFordShortestPath).