|
Обозначим через МинСт(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;
Это - алгоритмом динамического программирования, или алгоритмом Форда - Беллмана.
Программа останется правильной , даже если не заводить массива y, а производить изменения в самом массиве x
(заменив в программе все вхождения буквы y на x и затем удалить
ставшие лишними строки).
Этот алгоритм может быть улучшен в двух отношениях: можно за то же время O(n3) найти наименьшую стоимость проезда i->j для ВСЕХ пар i,j (а не только с i=1), а можно сократить время работы до O(n в степени 2). Правда, в последнем случае нам потребуется, чтобы все цены a[i][j] были неотрицательны.
|
