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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Строка 11: Строка 11:
=== Информационный граф ===
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Описание ресурса параллелизма алгоритма ===
[[Алгоритм Δ-шагания]] может рассматриваться как параллельная версия алгоритма Беллмана-Форда.
=== Описание входных и выходных данных ===
=== Описание входных и выходных данных ===
=== Свойства алгоритма===
=== Свойства алгоритма===

Версия от 16:18, 11 июня 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=1887