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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Входные данные:
  граф с вершинами 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)

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

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

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

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

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

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

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

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

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