Алгоритм Флойда

Этот алгоритм решает задачу нахождения кратчайших путей между всеми парами вершин графа. Более строгая формулировка этой задачи следующая: есть ориентированный граф G = (V, Е), каждой дуге (v, w) этого графа сопоставлена неотрицательная стоимость C [ v, w ]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, w) любого пути от вершины v в вершину w, длина которого минимальна среди всех возможных путей от v к w.

Можно решить эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но существует прямой способ решения данной задачи, использующий алгоритм Флойда. Для определенности положим, что вершины графа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу A размера n ´ n, в которой вычисляются длины кратчайших путей. В начале A [ i, j ] = C [ i, j ] для всех i <> j. Если дуга (i, j) отсутствует, то C [ i, j ] = ¥. Каждый диагональный элемент матрицы A равен 0.

Над матрицей A выполняется n итераций. После k -й итерации A [ i, j ] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и j могут находиться только вершины, номера которых меньше или равны k.

На k -й итерации для вычисления матрицы A применяется следующая формула: А _k [ i, j ] = min (A_{k -1}[ i, j ], A_{k -1}[ i, k ] + A_{k -1}[ k, j ]).

Нижний индекс k обозначает значение матрицы А после k -й итерации, но это не означает, что существует n различных матриц, этот индекс используется для сокращения записи.

Равенства A_k [ i, k ] = A_{k -1}[ i, k ] и A_k [ k, j ] = A_{k -1}[ k, j ] означают, что на k -й итерации элементы матрицы A, стоящие в k -й строке и k -м столбце, не изменяются. Более того, все вычисления можно выполнить с применением только одного экземпляра матрицы A. Представим алгоритм Флойда в виде следующей процедуры.

procedure Floyd (var A, P: array[1..n, 1..n] of real;

С: аrrау[1..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

A[i, j]:= A[i, k] + A[k, j];

P[i,j]:= k;

end;

Листинг 5.12 – Алгоритм Флойда, сохраняющий кратчайшие пути в матрице P

procedure path(i, j: integer);

var

k: integer;

begin

k:= P[i, j];

if k = 0 then return;

path(d, k);

writeln(k);

path(k, j)

end; {path }

Листинг 5.13 – Алгоритм вывода на печать кратчайшего пути из i в j

Рисунок 5.12 – Уточнение кратчайшего пути из вершины i в вершину j

Рисунок 5.13 – Работа алгоритма Флойда

Следует заметить, что если в графе существует контур отрицательной суммарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, «прокрутившись» в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае, описанном выше, алгоритм Флойда не применим. Останавливаясь подробнее надо заметить, что если граф неориентированный, то ребро с отрицательным весом является как раз таким контуром (проходя по нему в обоих направлениях столько раз пока не сделаем вес достаточно малым).

Заметим, что если граф неориентированный, то все матрицы, получаемые в результате преобразований симметричны и, следовательно, достаточно вычислять только элементы расположенные выше главной диагонали.

Время выполнения этого алгоритма, очевидно, имеет порядок O (n ³), поскольку в нем присутствуют вложенные друг в друга три цикла.