Обозначим через МинСт(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] были неотрицательны.  8  Комментарии к статье  8 8  Обсудить в чате