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

Алгоритмы Дийкстры и Форда предназначены для поиска длин кратчайших путей из данной вершины sв остальные вершины графа. При решении прикладных задач часто бывает необходимо найти длины кратчайших путей из каждой вершины графа в каждую из остальных. Задача может быть решенаN-кратным применением алгоритма Форда, однако более прост и эффективен алгоритм Флойда, специально предназначенный для этой цели. ОбозначимD⁰={d_ij⁰} матрицу длин ребер данного графа, причемd_ii⁰=0,d_ij⁰=, если ребра(i,j)в графе нет,d_ij⁰=a_ijв остальных случаях. МатрицуD⁰ можно считать матрицей длин кратчайших путей, проходящих через 0 промежуточных вершин. Далее в алгоритме Флойда последовательно вычисляются матрицы D¹,…, D^N, где матрицаD^k является матрицей длин кратчайших путей, проходящих через вершины1,…,k. Пусть матрицаD^k-1={d_ij^k-1} известна. Кратчайший путь изiвj, проходящий через вершины1,…,k, либо проходит через вершинуk, либо нет. Во втором случае его длинаd_ij^k равнаd_ij^k-1, а в первом он является объединением кратчайших путей через1…k-1изiвkи изkвj, поэтому

d_ij^k=min{ d_ij^k-1, d_ik^k-1+d_kj^k-1}.

Теперь можно описать алгоритм Флойда

Шаг 1. Построить матрицу D⁰,

Шаг 2. Для k=1,…,Nвычислить матрицыD¹,…, D^Nпо правилуd_ij^k=min{ d_ij^k-1, d_ik^k-1+d_kj^k-1}.

Рис 2.10

Пример 4. Для графа на рис. 2.10 вычисление длин кратчайших путей по алгоритму Флойда приводит к следующим результатам:

Матрица D⁶является матрицей длин кратчайших путей данного графа. Наличие в ней элементов, равных бесконечности, означает, что для данных пар узлов ни одного пути в графе не имеется. Сами пути могут быть найдены по матрицамD⁰иD⁶с помощью «обратного просмотра». Например, для пути из 1 в 6 последней вершиной является 6, а предпоследней должна быть вершинаkтакая, чтоd_1,6⁶=d_1,k⁶+d_k,6⁰. Легко видеть, что это вершина 4. Далее аналогично можно найти вершину, предшествующую 4, и так далее, до вершины 1. В итоге получается путь {1,3,5,4,6}.