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

Алгоритм Флойда — Уоршелла
Назван в честь	Роберт Флойд и Стивен Уоршелл
Автор	Бернар Руа[вд]
Предназначение	поиск в графе кратчайших путей между любыми парами вершин
Структура данных	граф
Худшее время	${\displaystyle \Theta (|V|^{3})}$
Лучшее время	${\displaystyle \Theta (|V|^{3})}$
Среднее время	${\displaystyle \Theta (|V|^{3})}$
Затраты памяти	${\displaystyle \Theta (|V|^{2})}$
Медиафайлы на Викискладе

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

Пусть вершины графа ${\displaystyle G=(V,\;E),\;|V|=n}$ пронумерованы от 1 до ${\displaystyle n}$ и введено обозначение ${\displaystyle d_{ij}^{k}}$ для длины кратчайшего пути от ${\displaystyle i}$ до ${\displaystyle j}$, который кроме самих вершин ${\displaystyle i,\;j}$ проходит только через вершины ${\displaystyle 1\ldots k}$. Очевидно, что ${\displaystyle d_{ij}^{0}}$ — длина (вес) ребра ${\displaystyle (i,\;j)}$, если таковое существует (в противном случае его длина может быть обозначена как ${\displaystyle \infty }$).

Существует два варианта значения ${\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)}$:

1. Кратчайший путь между ${\displaystyle i,\;j}$ не проходит через вершину ${\displaystyle k}$, тогда ${\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}$
2. Существует более короткий путь между ${\displaystyle i,\;j}$, проходящий через ${\displaystyle k}$, тогда он сначала идёт от ${\displaystyle i}$ до ${\displaystyle k}$, а потом от ${\displaystyle k}$ до ${\displaystyle j}$. В этом случае, очевидно, ${\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}$

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

Тогда рекуррентная формула для ${\displaystyle d_{ij}^{k}}$ имеет вид:

${\displaystyle d_{ij}^{0}}$ — длина ребра ${\displaystyle (i,\;j);}$

${\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}$

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения ${\displaystyle d_{ij}^{k},}$ ${\displaystyle \forall i,\;j}$ для ${\displaystyle k}$ от 1 до ${\displaystyle n}$. Полученные значения ${\displaystyle d_{ij}^{n}}$ являются длинами кратчайших путей между вершинами ${\displaystyle i,\;j.}$

На каждом шаге алгоритм генерирует матрицу ${\displaystyle W,}$ ${\displaystyle w_{ij}=d_{ij}^{n}.}$ Матрица ${\displaystyle W}$ содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица ${\displaystyle W}$ заполняется длинами рёбер графа (или запредельно большим M, если ребра нет).

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

Три вложенных цикла содержат операцию, исполняемую за константное время. ${\displaystyle \sum _{n,\;n,\;n}O(1)=O(n^{3}),}$ то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать в матрицу идентификатор первого узла в пути.

Алгоритм Флойда-Уоршелла может быть использован для нахождения замыкания отношения ${\displaystyle E}$ по транзитивности. Для этого в качестве W[0] используется бинарная матрица смежности графа, ${\displaystyle ({w^{0}}_{ij})_{n\times n}=1\Leftrightarrow (i,\;j)\in E}$; оператор 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 является матрицей достижимости.

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

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет ${\displaystyle O(|V|\cdot |E|\log |V|)}$ при применении двоичной кучи, что лучше, чем ${\displaystyle O(|V|^{3})}$ алгоритма Флойда — Уоршелла тогда, когда ${\displaystyle |E|}$ существенно меньше ${\displaystyle |V|^{2}}$ (условие разреженности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел)^[2][3]. Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда — Уоршелла проявляется только на больших графах.

• Левитин А. В. Глава 11. Преодоление ограничений: Метод деления пополам // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 349—353. — 576 с. — ISBN 978-5-8459-0987-9
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.

Для улучшения этой статьи желательно: Проставить сноски, внести более точные указания на источники. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.