цикл} for i:=2
цикл}
for i:=2 to N do
for j:=1 to i-1 do if A[j,i]<>? then D[i]:=min(D[i],D[j]+A[j,i]);
end;
Время работы алгоритма пропорционально N2.
3.6.4. Кратчайшие пути между всеми парами вершин.
Алгоритм Флойда
Дано. Ориентированный граф G=<V,E> с матрицей весов A(array[1..N,1..N] of integer). Результат. Матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.
Идея алгоритма. Обозначим через Dm[i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..m]. Тогда имеем: D0[i,j]:=A[i,j] и D(m+1)[i,j]=min{Dm[i,j],Dm[i,m+1]+Dm[m+1,j]}. Второе равенство требует пояснения. Пусть мы находим кратчайший путь из i в j c промежуточными вершинами из множества [1..(m+1)]. Если этот путь не содержит вершину (m+1), то D(m+1)[i,j]=Dm[i,j]. Если же он содержит эту вершину, то его можно разделить на две части от i до (m+1) и от (m+1) до j.
Время работы алгоритма пропорционально N3.
procedure Distance; {A, D - глобальные
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
