Алгоритм Беллмана-Форда: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Teplov (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показано 40 промежуточных версий 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> у [[Алгоритм Дейкстры|алгоритма Дейкстры]]), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 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> | * Далее происходит <math>|V|-1</math> итерация, в ходе каждой из которых производится релаксация всех рёбер графа. | ||
Структуру можно описать следующим образом: | Структуру можно описать следующим образом: | ||
| Строка 27: | Строка 35: | ||
2. Релаксация множества рёбер <math>E</math> | 2. Релаксация множества рёбер <math>E</math> | ||
а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t | а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t' (z)=t(v)+ w(e)</math>. | ||
б) Если <math>t | б) Если <math>t' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math>). | ||
3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра. | 3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра. | ||
Если на <math> | Если на <math>|V|</math>-й итерации всё ещё производилась релаксацию рёбер, то в графе присутствует цикл отрицательной длины. Ребро <math>e=(v,z)</math>, лежащее на таком цикле, может быть найдено проверкой следующего условия (проверяется для всех рёбер за линейное время): <math>t(v)+w(e)<d(z)</math> | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| Строка 52: | Строка 60: | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Алгоритм выполняет <math> | Алгоритм выполняет <math>|V|-1</math> итерацию, на каждой из которых происходит релаксация <math>|E|</math> рёбер. Таким образом, общий объём работы составляет <math>O(|V||E|)</math> операций. | ||
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов. | Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов. | ||
| Строка 60: | Строка 68: | ||
=== Информационный граф === | === Информационный граф === | ||
На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма | На рисунке 1 представлен информационный граф алгоритма, демонстрирующий описанные уровни параллелизма. | ||
[[file:APSP.png|thumb|center|700px|Рисунок 1. Информационный граф обобщенного алгоритма Беллмана-Форда.]] | |||
На приведенном далее информационном графе нижний уровень параллелизма обозначен в горизонтальных плоскостях. Множество всех плоскостей представляет собой верхний уровень параллелизма (операции в каждой плоскости могут выполняться параллельно). | |||
[[ | Нижний уровень параллелизма на графе алгоритма расположен на уровнях [2] и [3], соответствующим операциям инициализации массива дистанций [2] и обновления массива c использованием данных массива ребер [3]. Операция [4] - проверка того, были ли изменения на последней итерации и выход из цикла, если таковых не было. | ||
Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями. | Верхний уровень параллелизма, как уже говорилось, заключается в параллельном подсчете дистанций для различных вершин-источников, и на рисунке отмечен разными плоскостями. | ||
| Строка 70: | Строка 80: | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
Алгоритм обладает значительным ресурсом параллелизма. Во-первых, поиск кратчайших путей от различных вершин может производиться независимо для каждой из вершин (параллельные вертикальные плоскости на рисунке 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>. | |||
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | [[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | ||
| Строка 76: | Строка 90: | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<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( | '''Объём входных данных''': <math>O(|V| + |E|)</math>. | ||
'''Выходные данные''' (возможные варианты): | '''Выходные данные''' (возможные варианты): | ||
| Строка 84: | Строка 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( | '''Объём выходных данных''': <math>O(|V|)</math>. | ||
=== Свойства алгоритма=== | === Свойства алгоритма=== | ||
| Строка 92: | Строка 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 части, отвечающей только за вычисления на графическом ускорителе. | ||
=== Результаты прогонов === | |||
=== | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
| Строка 131: | Строка 121: | ||
<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 части, отвечающей только за вычисления на графическом ускорителе.