Вход: непустой взвешенный граф G =(V, E) с произвольными весами ребер. Вершины графа пронумерованы от 1 до n. Граф G представлен матрицей смежности.

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

Алгоритм:

Пусть d_i,j^k – длина кратчайшего пути от i до j, который кроме самих вершин i, j проходит только через вершины 1…k.

При этом матрица смежности D⁰ = ( d_i,j⁰ ).

Для d_i,j^k возможны два варианта (выбирается минимальный из них с учётом способа указания в матрице смежности несуществующих рёбер):

1) Кратчайший путь между i и j не проходит через вершину k, тогда d_i,j^k = d_i,j^k-1.

2) Существует более короткий путь между i и j, проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, d_i,j^k = d_i,k^k-1 + d_k,j^k-1.

Алгоритм Флойда последовательно вычисляет все значения d_i,j^k, для k от 1 до n. Полученные значения d_i,jⁿ являются длинами кратчайших путей между вершинами i и j. Решением является матрица Dⁿ = ( d_i,jⁿ ).

Сложность алгоритма Флойда составляет O(n³).