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

[непроверенная версия]

Версия 22:01, 11 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

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

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

Алгоритм Беллмана-Форда^[1]^[2]^[3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [math]O(mn)[/math] против [math]O(m + n\ln n)[/math] у алгоритма Дейкстры), однако его отличительной особенностью является применимость к графам с произвольными, в том числе отрицательными, весами.

1.2 Математическое описание

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

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

1.6 Последовательная сложность алгоритма

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

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

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

1.9 Описание входных и выходных данных

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

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

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

2.2 Описание локальности данных и вычислений

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

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.7 Существующие реализации алгоритма

Boost Graph Library (функция bellman_ford_shortest).
Python: NetworkX (функция bellman_ford).

3 Литература

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

[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,” 285–92, 1959.

[1]

[2]

[3]

@@ Строка 16: / Строка 16: @@
 === Описание входных и выходных данных ===
 === Свойства алгоритма===
+Алгоритм может распознавать наличие отрицательных циклов в графе. Ребро <math>e = (v, w)</math> лежит на таком цикле, если вычисленные алгоритмом кратчайшие расстояния <math>d(v)</math> удовлетворяют условию
+:<math>
+        d(v) + f(e) < d(w),
+</math>
+где <math>f(e)</math> – вес ребра <math>e</math>. Условие может быть проверено для всех рёбер графа за время <math>O(m)</math>.
 == Программная реализация алгоритмов ==
 === Особенности реализации последовательного алгоритма ===