Изменения

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

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

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

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

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

<mathtex>d_{i j}^{k} = \min (d_{i j}^{k-1},\; d_{i k}^{k-1} + d_{k j}^{k-1})</mathtex>

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

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

'''for''' k = 1 '''to''' n '''for''' i = 1 '''to''' n '''for''' j = 1 '''to''' n

<mathtex>\sum_{n,\;n,\;n}O(1) = O(n^3),</mathtex>

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

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