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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 Свойства алгоритма

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

[math] d(v) + f(e) \lt d(w), [/math]

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

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

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

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