Алгоритм нахождения расстояния от источника до всех вершин - метод Форда - Беллмана

Алгоритм нахождения расстояния от источника до всех вершин - 

метод Форда - Беллмана

Данные: Ориентированный граф •V, E• с n вершинами с выделенным источником s ∈ V, матрица дуг A[u, v], u, v ∈V (граф не содержит контуров отрицательной длины).

Результаты: Расстояния от источника до всех вершин графа: D[v]=d(s, v), v∈ V.

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 1 (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 дугами содержит контур, устранение которого не увеличивает длины пути (ведь мы предполагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма.