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

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

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

Алгоритм Беллмана-Форда предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [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 each e = (w, v) ∈ E:
        if d(v) > d(w) + f(e):
            d(v) := d(w) + f(e)

Последовательная сложность алгоритма

Алгоритм выполняет [math]\displaystyle{ n-1 }[/math] итерацию, на каждой из которых происходит релаксация [math]\displaystyle{ m }[/math] рёбер. Таким образом, общий объём работы составляет [math]\displaystyle{ O(mn) }[/math] операций.

Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.

1. Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
2. На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).

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

При использовании атомарных операций для вычисления минимума релаксация рёбер может производится параллельно. В этом случае потребуется [math]\displaystyle{ O(n) }[/math] шагов при использовании [math]\displaystyle{ O(m) }[/math] процессоров.

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

Описание входных и выходных данных

Входные данные: взвешенный граф [math]\displaystyle{ (V, E, W) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер [math]\displaystyle{ e_j = (v^{(1)}_{j}, v^{(2)}_{j}) }[/math] с весами [math]\displaystyle{ f_j }[/math]), вершина-источник [math]\displaystyle{ u }[/math].

Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].

Выходные данные (возможные варианты):

1. для каждой вершины [math]\displaystyle{ v }[/math] исходного графа – последнее ребро [math]\displaystyle{ e^*_v = (w, v) }[/math], лежащее на кратчайшем пути от вершины [math]\displaystyle{ u }[/math] к [math]\displaystyle{ v }[/math], или соответствующая вершина [math]\displaystyle{ w }[/math];
2. для каждой вершины [math]\displaystyle{ v }[/math] исходного графа – суммарный вес [math]\displaystyle{ f^*(v) }[/math] кратчайшего пути от от вершины [math]\displaystyle{ u }[/math] к [math]\displaystyle{ v }[/math].

Объём выходных данных: [math]\displaystyle{ O(n) }[/math].

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

Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро [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).