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

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

поиск в графе кратчайшего пути из одной вершины во все остальные

Структура данных

граф

Худшее время

Лучшее время

Среднее время

Затраты памяти


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

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

Пусть вершины графа пронумерованы от 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 (1959). «Transitivité et connexité.». C. R. Acad. Sci. Paris (англ.) 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 .

Литература[править | править вики-текст]