Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда | |
Последовательный алгоритм | |
Последовательная сложность | O(|V||E|) |
Объём входных данных | O(|V| + |E|) |
Объём выходных данных | O(|V|^2) |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | N/A, max O(|V|) |
Ширина ярусно-параллельной формы | O(|E|) |
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Беллмана-Форда[1][2][3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность O(|V||E|) против O(|E| + |V|\ln(|V|)) у алгоритма Дейкстры), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.
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.
- Далее происходит |V|-1 итерация, в ходе каждой из которых производится релаксация всех рёбер графа.
Структуру можно описать следующим образом:
1. Инициализация: всем вершинам присваивается предполагаемое расстояние t(v)=\infty, кроме вершины-источника, для которой t(u)=0 .
2. Релаксация множества рёбер E
а) Для каждого ребра e=(v,z) \in E вычисляется новое предполагаемое расстояние t' (z)=t(v)+ w(e).
б) Если t' (z)\lt t(z), то происходит присваивание t(z) := t' (z) (релаксация ребра e).
3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.
Если на |V|-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро e=(v,z), лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): t(v)+w(e)\lt d(z)
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 each e = (w, v) ∈ E: if d(v) > d(w) + f(e): d(v) := d(w) + f(e)
1.6 Последовательная сложность алгоритма
Алгоритм выполняет |V|-1 итерацию, на каждой из которых происходит релаксация |E| рёбер. Таким образом, общий объём работы составляет O(|V||E|) операций.
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
- Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
- На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).
1.7 Информационный граф
На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.
На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).
Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.
Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями.
1.8 Ресурс параллелизма алгоритма
Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 1). Во-вторых, поиск кратчайших путей от фиксированной вершины u также может выполняться параллельно: инициализация начальных путей [2] требует |V| параллельных операции, релаксация каждого ребра требует O(|E|) параллельных операции.
Таким образом, при наличии O(|E|) процессоров алгоритм завершит работу максимум за |V| шагов. В реальности, шагов обычно требуется меньше, а именно O(r) -(максимальная длина среди всех кратчайших путей от выбранной вершины-источника u).
Таким образом, ширина ярусно-параллельной формы алгоритма равна O(|E|), высота ЯПФ - O(r) | r \lt |V|.
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
1.9 Входные и выходные данные алгоритма
Входные данные: взвешенный граф (V, E, W) (|V| вершин v_i и |E| рёбер e_j = (v^{(1)}_{j}, v^{(2)}_{j}) с весами f_j), вершина-источник u.
Объём входных данных: O(|V| + |E|).
Выходные данные (возможные варианты):
- для каждой вершины v исходного графа – последнее ребро e^*_v = (w, v), лежащее на кратчайшем пути от вершины u к v, или соответствующая вершина w;
- для каждой вершины v исходного графа – суммарный вес f^*(v) кратчайшего пути от от вершины u к v.
Объём выходных данных: O(|V|).
1.10 Свойства алгоритма
Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро e = (v, w) лежит на таком цикле, если вычисленные алгоритмом кратчайшие расстояния d(v) удовлетворяют условию
- d(v) + f(e) \lt d(w),
где f(e) – вес ребра e. Условие может быть проверено для всех рёбер графа за время O(|E|).
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе.