Алгоритм Флойда (кратчайшие пути между всеми парами вершин)
Пусть требуется найти кратчайшие пути между всеми парами вершин графа. Очевидный способ получить ответ на этот вопрос заключается в n- кратном применении алгоритма Дейкстры или алгоритма Форда, причем каждый раз в качестве начальной вершины s берутся различные вершины.
В случае полного графа с неотрицательной матрицей весов C время, необходимое для вычислений, пропорционально
, а для произвольной матрицы весов оно пропорционально 
. Опишем совершенно иной подход к задаче нахождения кратчайших путей между всеми парами вершин. Этот метод применим как к неотрицательным, так и к произвольным матрицам весов и время, необходимое для вычислений, пропорционально 
. Если этот метод применим к графам с неотрицательной матрицей весов, то он сэкономит почти 50 % времени по сравнению с n-кратным применением алгоритма Дейкстры. Метод был предложен первоначально Флойдом. Он базируется на использовании последовательности из n преобразований (итераций) начальной матрицы весов С. При этом на k-й итерации матрица представляет длины кратчайших путей между каждой парой вершин с тем ограничением, что путь между 
и 
(для любых и ) содержит в качестве промежуточных только вершины из множества 
.
Описание алгоритма Флойда:
Предположим, что в начальной матрице весов 
для всех 
и 
, если в графе отсутствует дуга 
.
Шаг 1. Присвоить 
.
Шаг 2. 
.
Шаг 3. Для всех 
, таких, что 
, и для всех 
, таких, что 
, введем операцию
. (1.3)
Шаг 4.
1. Если 
, то в графе G существует цикл отрицательного веса, содержащий вершину , и решения нет.
2. Если все 
и 
, то получено решение. Матрица 
дает длины всех кратчайших путей.
3. Если все , но 
, то вернуться к шагу 2.
Сами кратчайшие пути можно найти по их длинам с помощью рекурсивной процедуры, подобной той, которая выше определялась соотношением (1.2). С другой стороны, можно использовать информацию о самих путях (наряду с информацией о длинах путей). Этот последний метод полезен в тех случаях, когда требуется найти в графе цикл отрицательного веса (если такой существует). В этом методе в дополнение к матрице весов C хранится и обновляется вторая 
-матрица 
.
указывает вершину, непосредственно предшествующую вершине в кратчайшем пути от к . Матрице 
присваиваются начальные значения 
для всех и . В соответствии с (1.3) на шаге 3 алгоритма обновление матрицы происходит так: 
.
В конце алгоритма кратчайшие пути получаются непосредственно из заключительной матрицы . Таким образом, кратчайший путь между двумя вершинами и дается следующей последовательностью вершин:
,
где 
, 
, 
и т.д. до 
.
Здесь следует отметить, что если всем 
придать начальные значения ∞ (а не 0), то конечное значение величины 
будет равно весу цепи, проходящей через вершину . Исходя из структуры матрицы , полученной в процессе той итерации, когда элемент становится отрицательным, можно найти цикл отрицательного веса, соответствующий этому элементу.