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

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

159

в вершину 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 (рис. 54).

На 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: 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 A[i, j] := C[i, j]; 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]; end;

160

2

5

3

12 3

12 3

12 3

12 3

10 8 5

10 8 5

10 8 5

10 7 5

2 3 0»

2 3 0 8

2 3 0 8

2 3 0 8

3

оо

20

A₀

3 5 2 0

20

3

A₁ A₂

Рис. 54. Алгоритм Флойда

3 5 2 0

A₃

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

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

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