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

Алгоритм

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

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

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

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

Тогда рекуррентная формула для [math]d_{i j}^k[/math] имеет вид:

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

[math]d_{i j}^{k} = \min (d_{i j}^{k-1},\; d_{i k}^{k-1} + d_{k j}^{k-1})[/math]

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

Псевдокод

На каждом шаге алгоритм генерирует двумерную матрицу [math]W[/math], [math]w_{ij}=d_{i j}^n[/math]. Матрица [math]W[/math] содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица [math]W[/math] заполняется длинами рёбер графа.

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

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

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

Применение вариаций алгоритма

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

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

Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до [math]O(n^3 / k)[/math], где [math]k[/math] - длина битовой маски (в модели вычислений RAM).

Ссылки

• Реализация алгоритма Флойда на С++
• Реализация алгоритма Флойда на Delphi
• Визуализатор
• Википедия — свободная энциклопедия