Уровень алгоритма

Алгоритм Беллмана-Форда: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показаны 44 промежуточные версии 7 участников)
Строка 1: Строка 1:
 +
{{algorithm
 +
| name              = Алгоритм Беллмана-Форда
 +
| serial_complexity = <math>O(|V||E|)</math>
 +
| pf_height        = <math>N/A, max O(|V|) </math>
 +
| pf_width          = <math>O(|E|)</math>
 +
| input_data        = <math>O(|V| + |E|)</math>
 +
| output_data      = <math>O(|V|^2)</math>
 +
}}
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
'''Алгоритм Беллмана-Форда'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность <math>O(mn)</math> против <math>O(m + n\ln n)</math> у [[Алгоритм Дейкстры|алгоритма Дейкстры]]), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.
+
'''Алгоритм Беллмана-Форда'''<ref>Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.</ref><ref>Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.</ref><ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность <math>O(|V||E|)</math> против <math>O(|E| + |V|\ln(|V|))</math> у [[Алгоритм Дейкстры|алгоритма Дейкстры]]), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Строка 19: Строка 27:
 
Алгоритм последовательно уточняет значения функции <math>d(v)</math>.
 
Алгоритм последовательно уточняет значения функции <math>d(v)</math>.
 
* В самом начале производится присваивание <math>d(u) = 0</math>, <math>d(v) = \infty</math>, <math>\forall v \ne u</math>.
 
* В самом начале производится присваивание <math>d(u) = 0</math>, <math>d(v) = \infty</math>, <math>\forall v \ne u</math>.
* Далее происходит <math>n-1</math> итерация, в ходе каждой из которых производится релаксация всех рёбер графа.
+
* Далее происходит <math>|V|-1</math> итерация, в ходе каждой из которых производится релаксация всех рёбер графа.
  
 
Структуру можно описать следующим образом:
 
Структуру можно описать следующим образом:
Строка 27: Строка 35:
 
2. Релаксация множества рёбер <math>E</math>
 
2. Релаксация множества рёбер <math>E</math>
  
а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t^' (z)=t(v)+ w(e)</math>.
+
а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t' (z)=t(v)+ w(e)</math>.
  
б) Если <math>t^' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math> ).
+
б) Если <math>t' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math>).
  
 
3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.
 
3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.
  
Если на <math>n</math>-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро <math>e=(v,z)</math>, лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): <math>t(v)+w(e)<d(z)</math>
+
Если на <math>|V|</math>-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро <math>e=(v,z)</math>, лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): <math>t(v)+w(e)<d(z)</math>
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
Строка 52: Строка 60:
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
Алгоритм выполняет <math>n-1</math> итерацию, на каждой из которых происходит релаксация <math>m</math> рёбер. Таким образом, общий объём работы составляет <math>O(mn)</math> операций.
+
Алгоритм выполняет <math>|V|-1</math> итерацию, на каждой из которых происходит релаксация <math>|E|</math> рёбер. Таким образом, общий объём работы составляет <math>O(|V||E|)</math> операций.
  
 
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
 
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
Строка 60: Строка 68:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.
 +
 +
[[file:APSP.png|thumb|center|700px|Рисунок 1. Информационный граф обобщенного алгоритма Беллмана-Форда.]]
 +
 +
На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).
 +
 +
Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.
 +
 +
Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями.
 +
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
  
При использовании атомарных операций для вычисления минимума релаксация рёбер может производится параллельно. В этом случае потребуется <math>O(n)</math> шагов при использовании <math>O(m)</math> процессоров.
+
Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 1). Во-вторых, поиск кратчайших путей от фиксированной вершины <math>u</math> также может выполняться параллельно: инициализация начальных путей [2] требует <math>|V|</math> параллельных операции, релаксация каждого ребра требует <math>O(|E|)</math> параллельных операции.
 +
 
 +
Таким образом, при наличии <math>O(|E|)</math> процессоров алгоритм завершит работу максимум за <math>|V|</math> шагов. В реальности, шагов обычно требуется меньше, а именно <math>O(r)</math> -(максимальная длина среди всех кратчайших путей от выбранной вершины-источника <math>u</math>).
 +
 
 +
Таким образом, ширина ярусно-параллельной формы алгоритма равна <math>O(|E|)</math>, высота ЯПФ - <math>O(r) | r < |V|</math>.
  
 
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
 
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
Строка 68: Строка 90:
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
  
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.
+
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.
  
'''Объём входных данных''': <math>O(m + n)</math>.
+
'''Объём входных данных''': <math>O(|V| + |E|)</math>.
  
 
'''Выходные данные''' (возможные варианты):
 
'''Выходные данные''' (возможные варианты):
Строка 76: Строка 98:
 
# для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.
 
# для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.
 
 
'''Объём выходных данных''': <math>O(n)</math>.
+
'''Объём выходных данных''': <math>O(|V|)</math>.
  
 
=== Свойства алгоритма===
 
=== Свойства алгоритма===
Строка 84: Строка 106:
 
         d(v) + f(e) < d(w),
 
         d(v) + f(e) < d(w),
 
</math>
 
</math>
где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(m)</math>.
+
где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(|E|)</math>.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
+
 
==== Локальность реализации алгоритма ====
 
===== Структура обращений в память и качественная оценка локальности =====
 
===== Количественная оценка локальности =====
 
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
+
Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе.
==== Масштабируемость алгоритма ====
+
 
==== Масштабируемость реализации алгоритма ====
+
=== Результаты прогонов ===
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
 
 
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html bellman_ford_shortest]</code>).
 
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).
 
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html BellmanFordShortestPath]</code>).
 
  
 
== Литература ==
 
== Литература ==
Строка 108: Строка 121:
 
<references />
 
<references />
  
[[Категория:Начатые статьи]]
+
[[Категория:Статьи в работе]]
 +
 
 +
[[En:Bellman-Ford algorithm]]

Текущая версия на 16:32, 4 июля 2022


Алгоритм Беллмана-Форда
Последовательный алгоритм
Последовательная сложность [math]O(|V||E|)[/math]
Объём входных данных [math]O(|V| + |E|)[/math]
Объём выходных данных [math]O(|V|^2)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]N/A, max O(|V|) [/math]
Ширина ярусно-параллельной формы [math]O(|E|)[/math]

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

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

Алгоритм Беллмана-Форда[1][2][3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [math]O(|V||E|)[/math] против [math]O(|E| + |V|\ln(|V|))[/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]|V|-1[/math] итерация, в ходе каждой из которых производится релаксация всех рёбер графа.

Структуру можно описать следующим образом:

1. Инициализация: всем вершинам присваивается предполагаемое расстояние [math]t(v)=\infty[/math], кроме вершины-источника, для которой [math]t(u)=0[/math] .

2. Релаксация множества рёбер [math]E[/math]

а) Для каждого ребра [math]e=(v,z) \in E[/math] вычисляется новое предполагаемое расстояние [math]t' (z)=t(v)+ w(e)[/math].

б) Если [math]t' (z)\lt t(z)[/math], то происходит присваивание [math]t(z) := t' (z)[/math] (релаксация ребра [math]e[/math]).

3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.

Если на [math]|V|[/math]-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро [math]e=(v,z)[/math], лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): [math]t(v)+w(e)\lt d(z)[/math]

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

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

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

for each vV 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 Последовательная сложность алгоритма

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

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

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

1.7 Информационный граф

На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма.

Рисунок 1. Информационный граф обобщенного алгоритма Беллмана-Форда.

На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно).

Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было.

Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями.

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

Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 1). Во-вторых, поиск кратчайших путей от фиксированной вершины [math]u[/math] также может выполняться параллельно: инициализация начальных путей [2] требует [math]|V|[/math] параллельных операции, релаксация каждого ребра требует [math]O(|E|)[/math] параллельных операции.

Таким образом, при наличии [math]O(|E|)[/math] процессоров алгоритм завершит работу максимум за [math]|V|[/math] шагов. В реальности, шагов обычно требуется меньше, а именно [math]O(r)[/math] -(максимальная длина среди всех кратчайших путей от выбранной вершины-источника [math]u[/math]).

Таким образом, ширина ярусно-параллельной формы алгоритма равна [math]O(|E|)[/math], высота ЯПФ - [math]O(r) | r \lt |V|[/math].

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

1.9 Входные и выходные данные алгоритма

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

Объём входных данных: [math]O(|V| + |E|)[/math].

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

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

Объём выходных данных: [math]O(|V|)[/math].

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(|E|)[/math].

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

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

2.2 Возможные способы и особенности параллельной реализации алгоритма

Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе.

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

  1. Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
  2. Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
  3. Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.