1 Begin

2 for v  V do D [v] := A[s, v]; D [s] := 0;

3 for k  := 1 to n – 2 do

4 for v  V \ {s} do

5 for u  V do D [v] := min(D[v], D[u] + A [u, v])

6 end

Докажем правильность этого алгоритма. Для этого обозначим через d^(m)(v) длину кратчайшего из путей из s в v, содержащих не более m дуг (d^(m)(v) = , если не существует ни одного такого пути). Тогда имеем

d^(m+1)(v) = min{d^(m)(u) + a[u, v]: u  V}, v  V. (1)

В самом деле, для каждого u  V очевидно имеем d^(m+1)(v)  d^(m)(u) + a[u, v], причем равенство появляется, когда u является предпоследней вершиной произвольного кратчайшего пути из s в v.

Покажем теперь, что если при входе в очередную итерацию цикла 3

d (s, v)  D[v]  d^(m)(v) для всех v  V, (2)

то по окончании этой итерации

d (s, v)  D[v]  d^(m+1)(v) для всех v  V. (3)

Действительно, предполагая выполнение условия (2) и анализируя действие оператора в строке 5, мы видим, что по окончании итерации цикла 3 имеем

d (s, v)  D[v]  min{d^(m)(u) + a[u, v]: u  V},

что, принимая во внимание равенство (1) дает условие (3).

Отметим, что при входе в цикл 3 имеем D[v] = d ¹ (v), v  V, следовательно, после выполнения n – 2 итераций этого цикла будут выполняться неравенства d (s, v)  D[v]  d^(n–1)(v), v  V.

Теперь достаточно показать, что d^(n–1)(v) = d (s, v). Это справедливо, поскольку каждый путь более чем с n – 1 дугами содержит контур, устранение которого не увеличивает длины пути (ведь мы предполагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма.

Очевидно, что временная сложность алгоритма есть O(n³). Мы можем, конечно, закончить вычисления, когда выполнение цикла 4 не вызывает изменения ни одной из переменных D[v], v  V. Это может наступить для k < n – 2, однако такая модификация алгоритма не изменяет существенным образом его сложности. Для редких графов (m << n²) удобнее представлять граф списками инцидентности ПРЕДШ[v], v  V. Заменяя строку 5 на

for u  ПРЕДШ[v] do D [v] := min(D[v], D[u] + A [u, v]),

получаем алгоритм со сложностью O(nm).

Работа алгоритма Форда — Беллмана проиллюстрирована на следующем рисунке (V = {1, ..., 5}, веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).

2 (3) 3

(1) (3)

S = 1 (8) (2) (1)

(3) (-5)

5 (4) 4