Суть алгоритма Беллмана-Форда для поиска кратчайшего пути заключается в том, что он находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе, допуская рёбра с отрицательным весом. 12

Алгоритм работает в несколько фаз. 1 На каждой фазе просматриваются все рёбра графа, и алгоритм пытается произвести релаксацию вдоль каждого ребра — улучшить значение стоимости. 1 Фактически это значит, что он пытается улучшить ответ для вершины, пользуясь ребром и текущим ответом для вершины. 1

Алгоритм вычисляет кратчайшие пути снизу вверх. 3 Сначала он вычисляет самые короткие расстояния, то есть пути длиной не более, чем в одно ребро. 3 Затем он вычисляет кратчайшие пути длиной не более двух рёбер и так далее. 3

Также алгоритм Беллмана-Форда позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. 1