procedure Floyd( var A: array[1..n, 1..n] of real; С: array[l..n, 1..n] of real);
var
i, j, k: integer;
begin
for i: = 1 to n do
for j: = 1 to n do begin
A[i, j] := C[i, j];
P[i, j] := 0;
end;
for i := 1 to n do
A[i , i] := 0;
for k: = 1 to n do
for i: = 1 to n do
for j: = 1 to n do
if A[I,k] + A[k, j] < A[I, j] then begin
A[I, j] := A[I, k] + A[k, j];
P[I, j] := k;
end;
end; { Floyd}
Для вывода на печать последовательности узлов, составляющих кратчайший путь от узла до узла , вызывается процедура path(i,j), код которой приведен в листинге 4.2.2.
procedure раth ( i, j: integer );
var
k: integer ;
begin
k:= P[i, j];
if k = 0 then
return;
path(i, k);
writeln(k);
path(k, j)
end; { path }
Ввиду наличия трех вложенных циклов (см. листинг 4.2.1), временная сложность алгоритма Флойда равна .
Поскольку версия алгоритма Дейкстры с использованием матрицы смежности находит кратчайшие пути от одного узла за время порядка , то в этом случае применение алгоритма Дейкстры для нахождения всех кратчайших путей потребует времени порядка , т.е. получим такой же временной порядок, как и в алгоритме Флойда.
Константы пропорциональности в порядках времени выполнения для обоих алгоритмов зависят от применяемых компилятора и вычислительной машины, а также от особенностей реализации алгоритмов. Вычислительный эксперимент и измерение времени выполнения — самый простой путь подобрать лучший алгоритм для конкретного приложения.
Если , количество дуг в орграфе, значительно меньше, чем , тогда, несмотря на относительно малую константу в выражении порядка для алгоритма Флойда, целесообразно применять версию алгоритма Дейкстры со списками смежности. В этом случае время решения общей задачи нахождения кратчайших путей имеет порядок , что значительно лучше алгоритма Флойда, по крайней мере, для больших разреженных графов.
Во многих задачах интерес представляет только сам факт существования пути, длиной не меньше единицы, от узла до узла . Алгоритм Флойда можно приспособить для решения таких задач. Полученный в результате алгоритм еще до Флойда разработал Уоршелл (S. Warshall), поэтому его также называют алгоритмом Уоршелла.
Предположим, что матрица стоимостей совпадает с матрицей смежности для данного орграфа , т.е. только в том случае, если есть дуга , и , если такой дуги не существует. Требуется вычислить матрицу такую, что тогда и только тогда, когда существует путь от узла до узла длиной не менее 1 и — в противном случае. Такую матрицу часто называют транзитивным замыканием матрицы смежности.
Транзитивное замыкание можно вычислить с помощью процедуры, подобной Floyd, применяя на k-м шаге следующую формулу к булевой матрице :
.
Эта формула устанавливает, что существует путь от узла до узла , проходящий через узлы с номерами, не превышающими , только в следующих случаях.
1. Уже существует путь от узла до узла , который проходит через узлы с номерами, не превышающими .
2. Существует путь от узла до узла , проходящий через узлы с номерами, не превышающими , и путь от узла до узла , который также проходит через узлы с номерами, не превышающими .
Здесь, как и в алгоритме Флойда, и , то есть на -й итерации элементы матрицы , стоящие в -й строке и -м столбце, не изменяются. В отличие от алгоритма Флойда, для поиска пути длиной не меньше 1 от узла до узла на каждой итерации производится пересчет в том числе и диагональных элементов матрицы А.
Пример.Последовательные итерации при получении А3 - транзитивного замыкания матрицы смежности орграфа из рис. 4.2.3.
A0
A1
A2
A3
Программа Warshall вычисления транзитивного замыкания показана в листинге 4.2.3.
Листинг 4.2.3. Программа Warshall для вычисления транзитивного замыкания
procedure Marshall ( var A: array[l..n, l..n] of boolean; C: array[l..n, l..n] of boolean );
