Алгоритм Беллмана-Форда: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Беллмана-Форда'''<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(mn)</math> против <math>O(m + n\ln n)</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>. | ||
| Строка 21: | Строка 21: | ||
* Далее происходит <math>n-1</math> итерация, в ходе каждой из которых производится релаксация всех рёбер графа. | * Далее происходит <math>n-1</math> итерация, в ходе каждой из которых производится релаксация всех рёбер графа. | ||
=== | === Схема реализации последовательного алгоритма === | ||
Последовательный алгоритм реализуется следующим псевдокодом: | Последовательный алгоритм реализуется следующим псевдокодом: | ||
| Строка 46: | Строка 46: | ||
=== Информационный граф === | === Информационный граф === | ||
=== | === Ресурс параллелизма алгоритма === | ||
При использовании атомарных операций для вычисления минимума релаксация рёбер может производится параллельно. В этом случае потребуется <math>O(n)</math> шагов при использовании <math>O(m)</math> процессоров. | При использовании атомарных операций для вычисления минимума релаксация рёбер может производится параллельно. В этом случае потребуется <math>O(n)</math> шагов при использовании <math>O(m)</math> процессоров. | ||
| Строка 52: | Строка 52: | ||
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | [[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда. | ||
=== | === Входные и выходные данные алгоритма === | ||
'''Входные данные''': взвешенный граф <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>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>. | ||
| Строка 72: | Строка 72: | ||
где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(m)</math>. | где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(m)</math>. | ||
== Программная реализация | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности реализации | ==== Локальность реализации алгоритма ==== | ||
===== Структура обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
==== Масштабируемость алгоритма ==== | |||
==== Масштабируемость реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| Строка 88: | Строка 93: | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
Версия от 11:02, 29 июля 2015
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Беллмана-Форда[1][2][3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [math]\displaystyle{ O(mn) }[/math] против [math]\displaystyle{ O(m + n\ln n) }[/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{ n-1 }[/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{ n-1 }[/math] итерацию, на каждой из которых происходит релаксация [math]\displaystyle{ m }[/math] рёбер. Таким образом, общий объём работы составляет [math]\displaystyle{ O(mn) }[/math] операций.
Константа в оценке сложности может быть уменьшена за счёт использования следующих двух стандартных приёмов.
- Если на очередной итерации не произошло ни одной успешной релаксации, то алгоритм завершает работу.
- На очередной итерации рассматриваются не все рёбра, а только выходящие из вершин, для которых на прошлой итерации была выполнена успешная релаксация (на первой итерации – только рёбра, выходящие из источника).
Информационный граф
Ресурс параллелизма алгоритма
При использовании атомарных операций для вычисления минимума релаксация рёбер может производится параллельно. В этом случае потребуется [math]\displaystyle{ O(n) }[/math] шагов при использовании [math]\displaystyle{ O(m) }[/math] процессоров.
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
Входные и выходные данные алгоритма
Входные данные: взвешенный граф [math]\displaystyle{ (V, E, W) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер [math]\displaystyle{ e_j = (v^{(1)}_{j}, v^{(2)}_{j}) }[/math] с весами [math]\displaystyle{ f_j }[/math]), вершина-источник [math]\displaystyle{ u }[/math].
Объём входных данных: [math]\displaystyle{ O(m + n) }[/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(n) }[/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(m) }[/math].
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Boost Graph Library (функция
bellman_ford_shortest). - Python: NetworkX (функция
bellman_ford). - Java: JGraphT (класс
BellmanFordShortestPath).