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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 34: Строка 34:
 
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html bellman_ford_shortest]</code>).
 
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/bellman_ford_shortest.html bellman_ford_shortest]</code>).
 
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).
 
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).
 +
* Java: [http://jgrapht.org JGraphT] (класс [http://jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html BellmanFordShortestPath]).
  
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />

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

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 Существующие реализации алгоритма

3 Литература

  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,” International Symposium on the Theory of Switching, 285–92, 1959.