Алгоритм Флойда (поиск всех кратчайших путей в графе)

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе. Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры потребовала бы значительных вычислительных затрат.
Прежде чем представлять алгоритмы, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N. Обозначим через d_i,j^m длину кратчайшего пути из вершинм i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. (Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.) Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что d_i,j^m=∞. Из данного определения величин d_i,j^m следует, что величина d_i,j⁰, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим d_i,i^m= 0. Отметим далее, что величина d_i,j^mпредставляет длину кратчайшего пути между вершинами i и j.
Обозначим через D^m матрицу размера NxN, элемент (i, j) которой совпадает с d_i,j^m. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D⁰. Наша цель состоит в определении матрицы D^N, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.
В алгоритме Флойда в качестве исходной выступает матрица D⁰. Вначале из этой матрицы вычисляется матрица D¹. Затем по матрице D¹ вычисляется матрицав D² и т. д. Процесс повторяется до тех пор, пока по матрице D^N-1 не будет вычислена матрица D^N.
Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:

1. 1. кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m – 1) вершин;
   2. кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m – 1) вершин;
   3. кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m – 1) вершин.

Поскольку по предположению исходный граф не может содержать контуров отрицательной длины, один из двух путей — путь, совпадающий с представленным в пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 — должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых m вершин. Таким образом,

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}

Из соотношения видно, что для вычисления элементов матрицы D^m необходимо располагать лишь элементами матрицы D^m-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу. Теперь мм в состоянии датьформальное описание алгоритма Флойда для нахождения на графе кратчайших путей между всеми парами вершин.

Алгоритм

1. 1. Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D⁰, каждый элемент d_i,j  которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента d_i,iравным 0.
   2. Для целого m, последовательно принимающего значения 1…N определить по элементам матрицы D^m-1 элементы D^m
   3. Алгоритм заканчивается получением матрицы всех кратчайших путей D^N, N – число вершин графа.

Напомним, для определения по известным элементам матрицы D^m-1 элементов матрицы  D^m в алгоритме Флойда применяется рекурсивное соотношение:

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}

d_i,j^m – элемент матрицы D^m, d_i,j^m-1 – элементы матрицы D^m-1 найденой на предыдущем шаге алгоритма.
Пример