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