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

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

Алгоритм Флойда — Уоршелла
Назван в честь Роберт Флойд и Уоршелл, Стивен
Автор Bernard Roy[d]
Предназначение поиск в графе кратчайших путей между любыми парами вершин
Структура данных граф
Худшее время
Лучшее время
Среднее время
Затраты памяти
Commons-logo.svg Медиафайлы на Викискладе

АлгоритмПравить

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

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

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

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

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

  — длина ребра  

 

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

ПсевдокодПравить

На каждом шаге алгоритм генерирует матрицу     Матрица   содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица   заполняется длинами рёбер графа (или запредельно большим 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])

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

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

Вариации алгоритмаПравить

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

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

Сравнение с другими алгоритмамиПравить

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет   при применении двоичной кучи, что лучше, чем   алгоритма Флойда — Уоршелла тогда, когда   существенно меньше   (условие разреженности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

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

ПримечанияПравить

  1. Roy, Bernard. Transitivité et connexité. (неопр.) // C. R. Acad. Sci. Paris (англ.). — 1959. — Т. 249. — С. 216—218.
  2. Zwick, Uri (May 2002), All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM Т. 49 (3): 289–317, DOI 10.1145/567112.567114 .
  3. Chan, Timothy M. (January 2010), More algorithms for all-pairs shortest paths in weighted graphs, SIAM Journal on Computing Т. 39 (5): 2075–2089, DOI 10.1137/08071990x .

ЛитератураПравить