Русская Википедия:Алгоритм Флойда — Уоршелла
Шаблон:Алгоритм В информатике алгоритм Флойда-Уоршелла (также известный как алгоритм Флойда, алгоритм Роя-Уоршелла, алгоритм Роя-Флойда или алгоритм WFI) — это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма. Варианты алгоритма также могут быть использованы для поиска транзитивного замыкания отношения <math>R</math> или (в связи с системой голосования Шульце) наиболее широких путей между всеми парами вершин взвешенного графа.
История и именование
Алгоритм Флойда-Уоршелла является примером динамического программирования и был опубликован в своей ныне признанной форме Робертом Флойдом в 1962 году. Однако он по сути такой же, как алгоритмы, ранее опубликованные Бернардом Роем в 1959 году, а также Стивеном Уоршеллом в 1962 году для поиска транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликовано в 1956 г.) для преобразования детерминированного конечного автомата в регулярное выражение. Современная формулировка алгоритма в виде трех вложенных циклов for была впервые описана Питером Ингерманом также в 1962 году
Алгоритм
Рассмотрим граф <math>G</math> с вершинами <math>V</math>, пронумерованными от 1 до <math>N</math>. Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за <math>\Theta(|V|^3)</math> сравнений в графе, даже если в графе может быть до <math>\Omega (|V|^2)</math> ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.
Далее рассмотрим функцию <math>\mathrm{shortestPath}(i,j,k)</math>, которая возвращает кратчайший возможный путь от <math>i</math> до <math>j</math> с использованием вершин только из множества <math>\{1,2,\ldots,k\}</math> в качестве промежуточных точек на этом пути. Теперь, учитывая эту функцию, наша цель — найти кратчайший путь от каждого <math>i</math> до каждого <math>j</math>, используя любую вершину в <math>\{1,2,\ldots,N\}</math>.
Для каждой из этих пар вершин <math>\mathrm{shortestPath}(i,j,k)</math> может быть либо
- (1) путь, который не проходит через <math>k</math> (использует только вершины из набора <math>\{1,\ldots,k-1\}</math>),
или
- (2) путь, который проходит через <math>k</math> (от <math>i</math> до <math>k</math> и затем от <math>k</math> до <math>j</math>, в обоих случаях используются только промежуточные вершины в <math>\{1,\ldots,k-1\}</math>).
Мы знаем, что лучший путь от <math>i</math> до <math>j</math>, это путь который использует только вершины c <math>1</math> по <math>k-1</math>, определяется как <math>\mathrm{shortestPath}(i,j,k-1)</math>, и ясно, что если бы существовал лучший путь от <math>i</math> до <math>k</math> до <math>j</math>, тогда длина этого пути была бы цепочкой состоящей из самого короткого пути от <math>i</math> до <math>k</math> (только с использованием промежуточных вершин в <math>\{1,\ldots,k-1\}</math>) и кратчайшего пути от <math>k</math> до <math>j</math> (только с использованием промежуточных вершин в <math>\{1,\ldots,k-1\}</math>).
Если <math>w(i,j)</math> — вес ребра между вершинами <math>i</math> и <math>j</math>, мы можем определить <math>\mathrm{shortestPath}(i,j,k)</math> в терминах следующей рекурсивной формулой:
базовый случай
- <math>\mathrm{shortestPath}(i,j,0) = w(i,j)</math>
и рекурсивный случай
- <math>\mathrm{shortestPath}(i,j,k) =</math>
- <math>\mathrm{min}\Big(\mathrm{shortestPath}(i,j,k-1),</math>
- <math>\mathrm{shortestPath}(i,k,k-1)+\mathrm{shortestPath}(k,j,k-1)\Big)</math>.
- <math>\mathrm{min}\Big(\mathrm{shortestPath}(i,j,k-1),</math>
Эта формула составляет основу алгоритма Флойда-Уоршелла. Алгоритм работает, сначала вычисляя <math>\mathrm{shortestPath}(i,j,k)</math> для всех пар <math>(i,j)</math> для <math>k=1</math>, а затем <math>k=2</math>, и так далее. Этот процесс продолжается до тех пор, пока <math>k=N</math> не будет найден кратчайший путь для всех пар <math>(i,j)</math> с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий:
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
Пример
Алгоритм выше выполняется на графе слева внизу:
Файл:Floyd-Warshall example.svg
До первой рекурсии внешнего цикла, обозначенного выше 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, обновленные расстояния выделены жирным шрифтом, будет иметь вид:
| Шаблон:Math | Шаблон:Mvar | ||||
| 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| Шаблон:Mvar | 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 3 | ∞ | |
| 3 | ∞ | ∞ | 0 | 2 | |
| 4 | ∞ | −1 | ∞ | 0 | |
| Шаблон:Math | Шаблон:Mvar | ||||
| 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| Шаблон:Mvar | 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ | |
| 3 | ∞ | ∞ | 0 | 2 | |
| 4 | ∞ | −1 | ∞ | 0 | |
| Шаблон:Math | Шаблон:Mvar | ||||
| 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| Шаблон:Mvar | 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ | |
| 3 | ∞ | ∞ | 0 | 2 | |
| 4 | 3 | −1 | 1 | 0 | |
| Шаблон:Math | Шаблон:Mvar | ||||
| 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| Шаблон:Mvar | 1 | 0 | ∞ | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 | |
| 3 | ∞ | ∞ | 0 | 2 | |
| 4 | 3 | −1 | 1 | 0 | |
| Шаблон:Math | Шаблон:Mvar | ||||
| 1 | 2 | 3 | 4 | ||
|---|---|---|---|---|---|
| Шаблон:Mvar | 1 | 0 | −1 | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 | |
| 3 | 5 | 1 | 0 | 2 | |
| 4 | 3 | −1 | 1 | 0 | |
Поведение с отрицательными циклами
Отрицательный цикл — это цикл, сумма ребер которого равна отрицательному значению. Не существует кратчайшего пути между любой парой вершин <math>i</math>, <math>j</math>, которые являются частью отрицательного цикла, потому что длина пути от <math>i</math> до <math>j</math> может быть сколь угодно малой (отрицательный). Для численно значимого вывода алгоритм Флойда-Уоршелла предполагает отсутствие отрицательных циклов. Тем не менее, если есть отрицательные циклы, алгоритм Флойда-Уоршелла может быть использован для их обнаружения. Очевидно, алгоритм заключается в следующем:
- Алгоритм Флойда-Уоршелла итеративно просматривает длину пути
между всеми парами вершин <math>(i,j)</math>, включая те где <math>i=j</math>;
- Изначально длина пути <math>(i,i)</math> равна нулю;
- Путь <math>[i,k,\ldots,i]</math> может улучшиться только в том случае, если его длина
меньше нуля, то есть обозначает отрицательный цикл;
- Таким образом, после алгоритма, <math>(i,i)</math> будет отрицательным, если
существует путь отрицательной длины от <math>i</math> до <math>i</math>.
Следовательно, чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда-Уоршелла, можно проверить диагональ матрицы кратчайших путей, и наличие отрицательного числа указывает на то, что граф содержит по крайней мере один отрицательный цикл. Во время выполнения алгоритма, если есть отрицательный цикл, могут появиться экспоненциально большие числа, вплоть до <math>\Omega(\cdot6^{n-1} w_{max})</math>, где <math>w_{max}</math> — наибольшее абсолютное значение отрицательного ребра в графе. Чтобы избежать проблем переполнения/потери значимости, следует проверять наличие отрицательных чисел на диагонали матрицы кратчайших путей внутри внутреннего цикла for алгоритма. Очевидно, что в неориентированном графе отрицательное ребро создает отрицательный цикл (то есть замкнутый обход), включающий его инцидентные вершины. Если рассматривать все ребра приведенного выше примера графа как неориентированные, то видно, что, например, последовательность вершин 4 — 2 — 4 представляет собой цикл с весовой суммой — 2.
Реконструкция путей
Алгоритм Флойда-Уоршелла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод восстановления фактического пути между любыми двумя вершинами конечной точки. Хотя кто-то может быть склонен хранить 3 фактический путь от каждой вершины к каждой другой вершине, это не обязательно, и на самом деле это очень дорого с точки зрения памяти. Вместо этого дерево кратчайших путей может быть вычислено для каждого узла за <math>\Theta(|E|)</math> время, используя память <math>\Theta(|V|)</math> для хранения каждого дерева, что позволяет нам эффективно реконструировать путь из любых двух связанных вершин.
Псевдокод[1]
let dist be a <math>|V| \times |V|</math> массив минимальных расстояний, инициализированный как <math>\infty</math> (бесконечность)
let next be a <math>|V| \times |V|</math> массив индексов вершин, инициализированный 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]
procedure Path(u, v)
if next[u][v] = null then
return []
path = [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
Анализ сложности Алгоритма
Пусть <math>n</math> будет <math>|V|</math> количеством вершин. Чтобы найти все <math>n^2</math> из <math>\mathrm{shortestPath}(i,j,k)</math> (для всех <math>i</math> и <math>j</math>) из <math>\mathrm{shortestPath}(i,j,k-1)</math>, требуется <math>2n^2</math> операций. Поскольку мы начинаем с <math>\mathrm{shortestPath}(i,j,0) = \mathrm{edgeCost}(i,j)</math> и вычисляем последовательность <math>n</math> матриц <math>\mathrm{shortestPath}(i,j,1)</math>, <math>\mathrm{shortestPath}(i,j,2)</math>, <math>\ldots</math>, <math>\mathrm{shortestPath}(i,j,n)</math>, общее количество используемых операций равно <math>n \cdot 2n^2 = 2n^3</math>. Следовательно, сложность алгоритма равна <math>\Theta(n^3)</math>.
Приложения и обобщения
Алгоритм Флойда-Уоршелла может быть использован для решения следующих задач, в частности:
- Кратчайшие пути в ориентированных графах (алгоритм Флойда)
- Транзитивное замыкание ориентированных графов (алгоритм Уоршелла). В оригинальной формулировке алгоритма Уоршелла граф не взвешен и представлен булевой матрицей смежности. Затем операция сложения заменяется логической конъюнкцией (И), а минимальная операция — логической дизъюнкцией (ИЛИ).
- Нахождение регулярного выражения, обозначающего регулярный язык, принимаемый конечным автоматом (алгоритм Клини, тесно связанное обобщение алгоритма Флойда-Уоршелла)
- Обращение вещественных матриц (алгоритм Гаусса-Жордана)
- Оптимальная маршрутизация. В этом приложении нужно найти путь с максимальным потоком между двумя вершинами. Это означает, что вместо взятия минимумов, как в псевдокоде выше, используются максимумы. Веса ребер представляют фиксированные ограничения для потока. Веса путей представляют собой узкие места поэтому операция сложения, указанная выше, заменяется минимальной операцией.
- Быстрый расчет сетей Pathfinder
- Самые широкие пути/пути с максимальной пропускной способностью
- Вычисление канонической формы матриц разностных границ (DBMs)
- Вычисление сходства между графами
Реализации
- Для C++, в библиотеке boost::graph
- Для C#, в QuickGraph
- Для C#, в QuickGraphPCL (Форк QuickGraph с лучшей совместимостью с проектами, использующими переносимые библиотеки классов.)
- Для Java, в библиотеке Apache Commons Graph
- Для JavaScript, в библиотеке Cytoscape
- Для MATLAB, в пакете Matlab_bgl
- Для Perl, в модуле Graph
- Для Python, в библиотеке SciPy (модуль scipy.sparse.csgraph) или в библиотеке NetworkX
- Для R, в пакете e1071 и Rfast
Сравнение с другими алгоритмами
Алгоритм Флойда-Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет <math>O(|V|\cdot|E|\log|V|)</math> при применении двоичной кучи, что лучше, чем <math>O(|V|^3)</math> алгоритма Флойда-Уоршелла тогда, когда <math>|E|</math> существенно меньше <math>|V|^2</math> (условие разреженности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.
Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел)[2][3]. Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда-Уоршелла проявляется только на больших графах.
Примечания
Литература
Шаблон:Алгоритмы поиска на графах
