| Алгоритм Флойда — Уоршелла |
| Назван в честь |
Роберт Флойд и Стивен Уоршелл |
| Автор |
Бернар Руа[d] |
| Предназначение |
поиск в графе кратчайших путей между любыми парами вершин |
| Структура данных |
граф |
| Худшее время |
| Лучшее время |
| Среднее время |
| Затраты памяти |
| Медиафайлы на Викискладе |
В информатике алгоритм Флойда-Уоршелла (также известный как алгоритм Флойда, алгоритм Роя-Уоршелла, алгоритм Роя-Флойда или алгоритм WFI) — это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма. Варианты алгоритма также могут быть использованы для поиска транзитивного замыкания отношения или (в связи с системой голосования Шульце) наиболее широких путей между всеми парами вершин взвешенного графа.
История и именование[правитьправить код]
Алгоритм Флойда-Уоршелла является примером динамического программирования и был опубликован в своей ныне признанной форме Робертом Флойдом в 1962 году. Однако он по сути такой же, как алгоритмы, ранее опубликованные Бернардом Роем в 1959 году, а также Стивеном Уоршеллом в 1962 году для поиска транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликовано в 1956 г.) для преобразования детерминированного конечного автомата в регулярное выражение. Современная формулировка алгоритма в виде трех вложенных циклов for была впервые описана Питером Ингерманом также в 1962 году
Алгоритм[правитьправить код]
Рассмотрим граф с вершинами , пронумерованными от 1 до . Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за сравнений в графе, даже если в графе может быть до ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.
Далее рассмотрим функцию , которая возвращает кратчайший возможный путь от до с использованием вершин только из множества в качестве промежуточных точек на этом пути. Теперь, учитывая эту функцию, наша цель — найти кратчайший путь от каждого до каждого , используя любую вершину в .
Для каждой из этих пар вершин может быть либо
(1) путь, который не проходит через (использует только вершины из набора ),
или
(2) путь, который проходит через (от до и затем от до , в обоих случаях используются только промежуточные вершины в ).
Мы знаем, что лучший путь от до , это путь который использует только вершины c по , определяется как , и ясно, что если бы существовал лучший путь от до до , тогда длина этого пути была бы цепочкой состоящей из самого короткого пути от до (только с использованием промежуточных вершин в ) и кратчайшего пути от до (только с использованием промежуточных вершин в ).
Если — вес ребра между вершинами и , мы можем определить в терминах следующей рекурсивной формулой:
базовый случай
и рекурсивный случай
.
Эта формула составляет основу алгоритма Флойда-Уоршелла. Алгоритм работает, сначала вычисляя для всех пар для , а затем , и так далее. Этот процесс продолжается до тех пор, пока не будет найден кратчайший путь для всех пар с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий:
let dist be a |V| × |V| массив минимальных расстояний, инициализированный как ∞ (бесконечность)
for each edge (u, v) do
dist[u][v] ← w(u, v) // Вес ребра (u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
Пример[правитьправить код]
Алгоритм выше выполняется на графе слева внизу:
До первой рекурсии внешнего цикла, обозначенного выше k = 0, единственные известные пути соответствуют отдельным ребрам в графе. При k = 1 находятся пути, проходящие через вершину 1: в частности, найден путь [2,1,3], заменяющий путь [2,3], который имеет меньше ребер, но длиннее (с точки зрения веса). При k = 2 находятся пути, проходящие через вершины 1,2. Красные и синие прямоугольники показывают, как путь [4,2,1,3] собирается из двух известных путей [4,2] и [2,1,3], встреченных в предыдущих итерациях, с 2 на пересечении. Путь [4,2,3] не рассматривается, потому что [2,1,3] — это кратчайший путь, встреченный до сих пор от 2 до 3. При k = 3 пути, проходящие через вершины 1,2,3 найдены. Наконец, при k = 4 находятся все кратчайшие пути.
Матрица расстояний на каждой итерации k, обновленные расстояния выделены жирным шрифтом, будет иметь вид:
| k = 0
|
j
|
| 1 |
2 |
3 |
4
|
| i
|
1
|
0 |
∞ |
−2 |
∞
|
| 2
|
4 |
0 |
3 |
∞
|
| 3
|
∞ |
∞ |
0 |
2
|
| 4
|
∞ |
−1 |
∞ |
0
|
| k = 1
|
j
|
| 1 |
2 |
3 |
4
|
| i
|
1
|
0 |
∞ |
−2 |
∞
|
| 2
|
4 |
0 |
2 |
∞
|
| 3
|
∞ |
∞ |
0 |
2
|
| 4
|
∞ |
−1 |
∞ |
0
|
| k = 2
|
j
|
| 1 |
2 |
3 |
4
|
| i
|
1
|
0 |
∞ |
−2 |
∞
|
| 2
|
4 |
0 |
2 |
∞
|
| 3
|
∞ |
∞ |
0 |
2
|
| 4
|
3 |
−1 |
1 |
0
|
| k = 3
|
j
|
| 1 |
2 |
3 |
4
|
| i
|
1
|
0 |
∞ |
−2 |
0
|
| 2
|
4 |
0 |
2 |
4
|
| 3
|
∞ |
∞ |
0 |
2
|
| 4
|
3 |
−1 |
1 |
0
|
| k = 4
|
j
|
| 1 |
2 |
3 |
4
|
| i
|
1
|
0 |
−1 |
−2 |
0
|
| 2
|
4 |
0 |
2 |
4
|
| 3
|
5 |
1 |
0 |
2
|
| 4
|
3 |
−1 |
1 |
0
|
Поведение с отрицательными циклами[правитьправить код]
Отрицательный цикл — это цикл, сумма ребер которого равна отрицательному значению. Не существует кратчайшего пути между любой парой вершин , , которые являются частью отрицательного цикла, потому что длина пути от до может быть сколь угодно малой (отрицательный). Для численно значимого вывода алгоритм Флойда-Уоршелла предполагает отсутствие отрицательных циклов. Тем не менее, если есть отрицательные циклы, алгоритм Флойда-Уоршелла может быть использован для их обнаружения. Очевидно алгоритм заключается в следующем:
- Алгоритм Флойда-Уоршелла итеративно просматривает длину пути
между всеми парами вершин , включая те где ;
- Изначально длина пути равна нулю;
- Путь может улучшиться только в том случае, если его длина
меньше нуля, то есть обозначает отрицательный цикл;
- Таким образом, после алгоритма, будет отрицательным, если
существует путь отрицательной длины от до .
Следовательно, чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда-Уоршелла, можно проверить диагональ матрицы кратчайших путей, и наличие отрицательного числа указывает на то, что граф содержит по крайней мере один отрицательный цикл. Во время выполнения алгоритма, если есть отрицательный цикл, могут появиться экспоненциально большие числа, вплоть до , где — наибольшее абсолютное значение отрицательного ребра в графе. Чтобы избежать проблем переполнения/потери значимости, следует проверять наличие отрицательных чисел на диагонали матрицы кратчайших путей внутри внутреннего цикла for алгоритма. Очевидно, что в неориентированном графе отрицательное ребро создает отрицательный цикл (то есть замкнутый обход), включающий его инцидентные вершины. Если рассматривать все ребра приведенного выше примера графа как неориентированные, то видно, что, например, последовательность вершин 4 — 2 — 4 представляет собой цикл с весовой суммой — 2.
Реконструкция путей[правитьправить код]
Алгоритм Флойда-Уоршелла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод восстановления фактического пути между любыми двумя вершинами конечной точки. Хотя кто-то может быть склонен хранить 3 фактический путь от каждой вершины к каждой другой вершине, это не обязательно, и на самом деле это очень дорого с точки зрения памяти. Вместо этого дерево кратчайших путей может быть вычислено для каждого узла за время, используя память для хранения каждого дерева, что позволяет нам эффективно реконструировать путь из любых двух связанных вершин.
Псевдокод[1][правитьправить код]
let dist be a массив минимальных расстояний, инициализированный как (бесконечность)
let next be a массив индексов вершин, инициализированный null
procedure FloydWarshallWithPathReconstruction() is
for each edge (u, v) do
dist[u][v] ← w(u, v) // Вес ребра (u, v)
next[u][v] ← v
for each vertex v do
dist[v][v] ← 0
next[v][v] ← v
for k from 1 to |V| do // стандартная реализация алгоритма Флойда–Уоршелла
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[i][k]
Подробнее ...
