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

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в (ор)графе. В этом алгоритме для хранения информации о путях используется матрица Н[1..р, 1..р], где

., _ J k, если k— первая вершина, достигаемая на кратчайшем пути из г в j; (О, если из i в j нет пути.

ОТСТУПЛЕНИЕ

Матрица Н размера О(р²) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе О(р²) путей, состоящих из О(р) вершин. Таким образом, не­посредственное представление всех путей потребовало бы памяти объема О(р³). Эконо­мия памяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном слу­чае любой конкретный путь (и, v) легко извлекается из матрицы с помощью следующего алгоритма.

w: =u; yield w{ первая вершина }

while w ^ v do

w : = H[w, v}; yield w{ следующая вершина }

end while

Алгоритм 8.З. алгоритм Флойда Вход: матрица С[1..р, 1..р] длин дуг.

Выход: матрица Т[1..р,1..р] длин путей и матрица Н[1..р,1..р] самих путей. for г from I to p do for j from 1 to p do T[i,j] : = C[i,j] { инициализация } if C[iJ] = 00 then

H[i,j\: = 0 { нет дуги из г в j } else

H[i,j] -=j{ есть дуга из г в j } end if end for end for

for г from 1 to p do for j from 1 to p do for fc from 1 to p do

if г + jkT{j,i] / <х>&г ф k&T{i,k] / oo&(T[j,fc] = ooVT[j,k] > T\ then

H[j, k]: = H[j, i] { запомнить новый путь } T[j, k]: = T[j, i] + T[i, k} { и его длину } end if end for end for

for j from 1 to p do ^if T,j <0then

stop { нет решения: вершина j входит в цикл отрицательной длины } end if end for end for

ЗАМЕЧАНИЕ -

Если в G есть цикл с отрицательным весом, то решения поставленной задачи не суще­ствует, так как можно «накручивать» на этом цикле сколь угодно короткий путь.

обоснование

Алгоритм Флойда имеет много общего с алгоритмом Уоршалла (алгоритм 1.8). Покажем по индукции, что после выполнения г-го шага основного цикла по г элементы матриц T\j,k\ и H[j,k] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути из вершины j в вершину k, про­ходящем через промежуточные вершины из диапазона 1..г. База: г = 0, то есть до начала цикла элементы матриц Т и Н содержат информацию о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вер­шины. Пусть теперь перед началом выполнения тела цикла на г-м шаге T[j, k] содержит длину кратчайшего пути от j к k , a H[j,k] содержит первую вершину на кратчайшем пути из вершины j в вершину k (если таковой есть). В таком случае, если в результате добавления вершины г к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда г = р, матрицы содержат кратчайшие пути, проходящие через промежуточ­ные вершины 1..р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Дополнительный цикл по j служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом.