147
правок
Изменения
Новая страница: «== Алгоритм == Пусть вершины графа <math>G=(V,\; E),\; |V| = n</math> пронумерованы от 1 до <math>n</math> и введен…»
== Алгоритм ==
Пусть вершины графа <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>d_{i j}^{0}</math> — длина (вес) ребра <math>(i,\;j)</math>, если таковое существует (в противном случае его длина может быть обозначена как <math>\infty</math>)
Существует два варианта значения <math>d_{i j}^{k},\;k \in \mathbb (1,\;\ldots,\;n)</math>:
# Кратчайший путь между <math>i,\;j</math> не проходит через вершину <math>k</math>, тогда <math>d_{i j}^{k}=d_{i j}^{k-1}</math>
# Существует более короткий путь между <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> по транзитивности. Для этого в качестве <code>W[0]</code> используется бинарная матрица смежности графа, <math>({w^0}_{i j})_{n \times n} = 1 \Leftrightarrow (i,\; j) \in E</math>; оператор <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])
После выполнения алгоритма матрица <code>W</code> является матрицей достижимости.
Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до <math>O(n^3 / k)</math>, где <math>k</math> - длина битовой маски (в модели вычислений RAM).
== Ссылки ==
* [http://e-maxx.ru/algo/floyd_warshall_algorithm Реализация алгоритма Флойда на С++]
* [http://plagiata.net.ru/?p=57 Реализация алгоритма Флойда на Delphi]
* [http://rain.ifmo.ru/cat/data/vis/graph-paths/floyd-warshall-2004/code.jar Визуализатор]
Пусть вершины графа <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>d_{i j}^{0}</math> — длина (вес) ребра <math>(i,\;j)</math>, если таковое существует (в противном случае его длина может быть обозначена как <math>\infty</math>)
Существует два варианта значения <math>d_{i j}^{k},\;k \in \mathbb (1,\;\ldots,\;n)</math>:
# Кратчайший путь между <math>i,\;j</math> не проходит через вершину <math>k</math>, тогда <math>d_{i j}^{k}=d_{i j}^{k-1}</math>
# Существует более короткий путь между <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> по транзитивности. Для этого в качестве <code>W[0]</code> используется бинарная матрица смежности графа, <math>({w^0}_{i j})_{n \times n} = 1 \Leftrightarrow (i,\; j) \in E</math>; оператор <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])
После выполнения алгоритма матрица <code>W</code> является матрицей достижимости.
Использование битовых масок при реализации алгоритма позволяет существенно ускорить алгоритм. При этом сложность алгоритма снижается до <math>O(n^3 / k)</math>, где <math>k</math> - длина битовой маски (в модели вычислений RAM).
== Ссылки ==
* [http://e-maxx.ru/algo/floyd_warshall_algorithm Реализация алгоритма Флойда на С++]
* [http://plagiata.net.ru/?p=57 Реализация алгоритма Флойда на Delphi]
* [http://rain.ifmo.ru/cat/data/vis/graph-paths/floyd-warshall-2004/code.jar Визуализатор]
