Алгоритм Беллмана-Форда: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показаны 54 промежуточные версии 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( | + | '''Алгоритм Беллмана-Форда'''<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> у [[Алгоритм Дейкстры|алгоритма Дейкстры]]), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами. |
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
Пусть задан граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math> и выделенной вершиной-источником <math>u</math>. Обозначим через <math>d(v)</math> кратчайшее расстояние от источника <math>u</math> до вершины <math>v</math>. | Пусть задан граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math> и выделенной вершиной-источником <math>u</math>. Обозначим через <math>d(v)</math> кратчайшее расстояние от источника <math>u</math> до вершины <math>v</math>. | ||
| Строка 14: | Строка 22: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | Основной операцией алгоритма является релаксация | + | Основной операцией алгоритма является релаксация ребра: если <math>e = (w, v) \in E</math> и <math>d(v) > d(w) + f(e)</math>, то производится присваивание <math>d(v) \leftarrow d(w) + f(e)</math>. |
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | Алгоритм последовательно уточняет значения функции <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)< 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)<d(z)</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>|V|-1</math> итерацию, на каждой из которых происходит релаксация <math>|E|</math> рёбер. Таким образом, общий объём работы составляет <math>O(|V||E|)</math> операций. | ||
| + | |||
| + | Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов. | ||
| + | |||
| + | # Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу. | ||
| + | # На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника). | ||
| + | |||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма. |
| + | |||
| + | [[file:APSP.png|thumb|center|700px|Рисунок 1. Информационный граф обобщенного алгоритма Беллмана-Форда.]] | ||
| + | |||
| + | На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно). | ||
| + | |||
| + | Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было. | ||
| + | |||
| + | Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями. | ||
| + | |||
| + | === Ресурс параллелизма алгоритма === | ||
| + | |||
| + | Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 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>. | ||
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | [[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | ||
| − | === | + | === Входные и выходные данные алгоритма === |
| + | |||
| + | '''Входные данные''': взвешенный граф <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>. | ||
| + | |||
| + | '''Выходные данные''' (возможные варианты): | ||
| + | # для каждой вершины <math>v</math> исходного графа – последнее ребро <math>e^*_v = (w, v)</math>, лежащее на кратчайшем пути от вершины <math>u</math> к <math>v</math>, или соответствующая вершина <math>w</math>; | ||
| + | # для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>. | ||
| + | |||
| + | '''Объём выходных данных''': <math>O(|V|)</math>. | ||
| + | |||
=== Свойства алгоритма=== | === Свойства алгоритма=== | ||
| Строка 31: | Строка 106: | ||
d(v) + f(e) < d(w), | d(v) + f(e) < d(w), | ||
</math> | </math> | ||
| − | где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O( | + | где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(|E|)</math>. |
| − | == Программная реализация | + | == Программная реализация алгоритма == |
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | ||
| − | === Возможные способы и особенности реализации | + | === Возможные способы и особенности параллельной реализации алгоритма === |
| − | + | Программа, реализующая алгоритм поиска кратчайших путей, состоит из двух частей: части, отвечающей за общую координацию вычислений, а также параллельные вычисления на многоядерных CPU, и GPU части, отвечающей только за вычисления на графическом ускорителе. | |
| − | === | + | |
| + | === Результаты прогонов === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
<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 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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) до каждой вершины 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 Последовательная сложность алгоритма
Алгоритм выполняет [math]|V|-1[/math] итерацию, на каждой из которых происходит релаксация [math]|E|[/math] рёбер. Таким образом, общий объём работы составляет [math]O(|V||E|)[/math] операций.
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
- Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
- На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).
1.7 Информационный граф
На рисунке 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].
Выходные данные (возможные варианты):
- для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
- для каждой вершины [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 части, отвечающей только за вычисления на графическом ускорителе.
