Поиск по сайту.


Другие алгоритмы.

Математика : Графы.

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

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




Вверх по странице, к оглавлению и навигации.