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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Следующая правка →
Общее описание алгоритма
 
Строка 21: Строка 21:
=== Выводы для классов архитектур ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
=== Существующие реализации алгоритма ===
* [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]).
== Литература ==
== Литература ==


<references />
<references />

Версия от 22:01, 10 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

  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.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Алгоритм_Беллмана-Форда&oldid=1824