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

Алгоритм

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

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

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

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

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

 — длина ребра

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

Псевдокод

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

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])

Сложность алгоритма

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

Вариации алгоритма

Построение матрицы достижимости

Алгоритм Флойда-Уоршелла может быть использован для нахождения замыкания отношения по транзитивности. Для этого в качестве 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 является матрицей достижимости.

Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до , где  — длина битовой маски (в модели вычислений 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