Алгоритм Беллмана-Форда
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Беллмана-Форда[1][2][3] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Беллмана-Форда масштабируется хуже других алгоритмов решения указанной задачи (сложность [math]\displaystyle{ O(mn) }[/math] против [math]\displaystyle{ O(m + n\ln 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].
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
bellman_ford_shortest). - Python: NetworkX (функция
bellman_ford).