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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритм[править | править вики-текст]

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

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

  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 имеет вид:

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

d_{i j}^{k} = \min (d_{i j}^{k-1},\; d_{i k}^{k-1} + d_{k j}^{k-1}).

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

Псевдокод[править | править вики-текст]

На каждом шаге алгоритм генерирует матрицу W, w_{ij}=d_{i j}^n. Матрица 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])

Сложность алгоритма[править | править вики-текст]

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

Вариации алгоритма[править | править вики-текст]

Построение матрицы достижимости[править | править вики-текст]

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

Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до O(n^3 / 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.
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.