Описание алгоритма Форда-Белмана

Алгоритм Ф.-Б. служит для поиска длин кратчайших путей от одной вершины до всех остальных в графах с весами ребер (в том числе алгоритм правильно работает если есть ребра отрицательного веса).

Для работы алгоритма понадобится массив B расстояний от начальной вершины до всех вершин. В начале расстояние до исходной вершины 0, до остальных - бесконечность.

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

N раз (где N - количество вершин графа) повторяем следующий шаг:

• Перебираем в любом порядке все ребра графа и для каждого ребра делаем следующее действие:
  • Пусть это ребро (u,v). Тогда если B[u] + вес ребра (u,v) < B[v], то в B[v] записываем новое значение, равное B[u] + вес ребра (u,v)

Обоснование. После того, как мы выполним первый шаг алгоритма, мы найдем длины путей, которые проходят не более, чем по одному ребру. На втором шаге мы попытаемся к этим путям добавить еще по одному ребру, т.е. найдем кратчайшие пути не более, чем из 2-х ребер. И так далее, после N-ого шага мы получим длины путей, состоящих не более, чем из N ребер.