Предполагается, что ориентированный граф не содержит контуров отрицательной длины

Алгоритм 3.1 (Алгоритм Форда – Беллмана). Основными вычисляемыми величинами этого алгоритма являются величины _j (k), где i = 1, 2, …, n (n – число вершин графа); k = 1, 2, …, n – 1. Для фиксированных i и k величина _j (k) равна длине минимального пути, ведущего из заданной начальной вершины х ₁ в вершину х_i и содержащего не более k дуг.

Шаг 1. Установка начальных условий. Ввести число вершин графа n и матрицу весов C = (c_ij).

Шаг 2. Положить k = 0. Положить _i (0) = ¥ для всех вершин, кроме х ₁; положить  ₁(0) = 0.

Шаг 3. В цикле по k, k = 1,..., n – 1, каждой вершине x_i на k -ом шаге приписать индекс _i (k) по следу­ющему правилу

: _i (k) = { _j (k – 1) + c_ji } для всех вершин, кроме х ₁, положить  ₁(k) = 0.

В результате работы алгоритма формируется таблица индексов _i (k), i = 1, 2, …, n, k = 0, 1, 2, …, n – 1. При этом _i (k) определяет длину минимального пути из первой вершины в i -ую, содержащего не более k дуг. 5. Восстановление минимального пути. Для любой вершины x_s предшествующая ей вершина x_r определяется из соотношения: _r (n – 2) + c_rs = _s (n – 1), x_r Î G^{- 1}(x_s), где G^{- 1}(x_s) - прообраз вершины x_s. Для найденной вершины x_r предшествующая ей вершина x_q определяется из соотношения: _q (n – 3) + c_qr = _r (n – 2), x_q Î G^{- 1}(x_r), где G^{- 1}(x_r) - прообраз вершины x_r, и т. д.

Последовательно применяя это соотношение, начиная от последней вершины x_i, найдем минимальный путь.