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

Задача. Найти наименьшую стоимость проезда из 1-го города во все остальные за время O(n³).
Решение. Обозначим через МинСт(1,s,к) наименьшую стоимость проезда из 1 в s менее чем с k пересадками. Тогда выполняется такое соотношение:

МинСт (1,s,k+1) = наименьшему из чисел МинСт(1,s,k) и
 МинСт(1,i,k) + a[i][s] (i=1..n)

Искомым ответом является МинСт(1,i,n) для всех i=1..n.

k:= 1;
 for i := 1 to n do begin x[i] := a[1][i]; end;
 {инвариант: x[i] := МинСт(1,i,k)}
 while k <> n do begin
 | for s := 1 to n do begin
 | | y[s] := x[s];
 | | for i := 1 to n do begin
 | | | if y[s] > x[i]+a[i][s] then begin
 | | | | y[s] := x[i]+a[i][s];
 | | | end;
 | | end
 | | {y[s] = МинСт(1,s,k+1)}
 | | for i := 1 to n do begin x[s] := y[s]; end;
 | end;
 | k := k + 1;
 end;

Приведенный алгоритм называют алгоритмом динамического программирования, или алгоритмом Форда - Беллмана.