Алгоритм Флойда–Уоршелла

Алгоритм Флойда–Уоршелла, динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом, хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Пусть вершины графа  пронумерованы от 1 до n и введено обозначение  для длины кратчайшего пути от i до j, который кроме самих вершин  проходит только через вершины . Очевидно, что  — длина (вес) ребра , если таковое существует (в противном случае его длина может быть обозначена как ).

Существует два варианта значения :

1. Кратчайший путь между  не проходит через вершину k, тогда 

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

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

Тогда рекуррентная формула для  имеет вид:

 — длина ребра 

А.Ф.-У. последовательно вычисляет все значения   для k от 1 до n. Полученные значения  являются длинами кратчайших путей между вершинами 

На каждом шаге алгоритм генерирует двумерную матрицу W,  Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрицаW заполняется длинами рёбер графа.

for k = 1 to n

for i = 1 to n

for j = 1 to n

W[i][j] = min(W[i][j], W[i][k] + W[k][j])

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

А.Ф.-У. может быть использован для нахождения замыкания отношения E по транзитивности. Для этого в качестве W[0] используется бинарная матрица смежности графа, ; оператор min заменяется дизъюнкцией, сложение заменяется конъюнкцией:

for k = 1 to n

for i = 1 to n

for j = 1 to n

W[i][j] = W[i][j] or (W[i][k] and W[k][j])

После выполнения алгоритма матрица W является матрицей достижимости.

Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до O(n3 / k), где k — длина битовой маски (в модели вычислений RAM). На практике, ещё бо́льшего ускорения можно достичь, используя такие специализированные наборы микропроцессорных команд, как SSE.

Лит.: Ананий В. Левитин Глава 8. Динамическое программирование: Алгоритм Флойда поиска кратчайших путей между всеми парами вершин // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms — М.: «Вильямс», 2006. — С. 349 — 353. — ISBN 0-201-74395-7. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.