Алгоритм Флойда — Уоршелла (Glikjnmb Slkw;g — Rkjoyllg)

Алгоритм Флойда — Уоршелла
Алгоритм Флойда — Уоршелла
Назван в честь	Роберт Флойд и Стивен Уоршелл
Автор	Бернар Руа[вд]
Предназначение	поиск в графе кратчайших путей между любыми парами вершин
Структура данных	граф
Худшее время
Лучшее время
Среднее время
Затраты памяти
	Медиафайлы на Викискладе

В информатике алгоритм Флойда — Уоршелла (также известный как алгоритм Флойда, алгоритм Роя — Уоршелла, алгоритм Роя — Флойда или алгоритм WFI) — это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма. Варианты алгоритма также могут быть использованы для поиска транзитивного замыкания отношения $R$ или (в связи с системой голосования Шульце) наиболее широких путей между всеми парами вершин взвешенного графа.

История и именование

Алгоритм Флойда — Уоршелла является примером динамического программирования и был опубликован в своей ныне признанной форме Робертом Флойдом в 1962 году. Однако он по сути такой же, как алгоритмы, ранее опубликованные Бернардом Роем в 1959 году, а также Стивеном Уоршеллом в 1962 году для поиска транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликовано в 1956 г.) для преобразования детерминированного конечного автомата в регулярное выражение. Современная формулировка алгоритма в виде трёх вложенных циклов «for» была впервые описана Питером Ингерманом также в 1962 году.

Алгоритм

Рассмотрим граф $G$ с вершинами $V$ , пронумерованными от 1 до $N$ . Алгоритм Флойда — Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за $\Theta (|V|^{3})$ сравнений в графе, даже если в графе может быть до $\Omega (|V|^{2})$ ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.

Далее рассмотрим функцию $\mathrm {shortestPath} (i,j,k)$ , которая возвращает кратчайший возможный путь от $i$ до $j$ с использованием вершин только из множества $\{1,2,\ldots ,k\}$ в качестве промежуточных точек на этом пути. Теперь, учитывая эту функцию, наша цель — найти кратчайший путь от каждого $i$ до каждого $j$ , используя любую вершину в $\{1,2,\ldots ,N\}$ .

Для каждой из этих пар вершин $\mathrm {shortestPath} (i,j,k)$ может быть либо

(1) путь, который не проходит через

k

(использует только вершины из набора

\{1,\ldots ,k-1\}

),

или

(2) путь, который проходит через

k

(от

i

до

k

и затем от

k

до

j

, в обоих случаях используются только промежуточные вершины в

\{1,\ldots ,k-1\}

).

Мы знаем, что лучший путь от $i$ до $j$ , это путь который использует только вершины c $1$ по $k-1$ , определяется как $\mathrm {shortestPath} (i,j,k-1)$ , и ясно, что если бы существовал лучший путь от $i$ до $k$ до $j$ , тогда длина этого пути была бы цепочкой состоящей из самого короткого пути от $i$ до $k$ (только с использованием промежуточных вершин в $\{1,\ldots ,k-1\}$ ) и кратчайшего пути от $k$ до $j$ (только с использованием промежуточных вершин в $\{1,\ldots ,k-1\}$ ).

Если $w(i,j)$ — вес ребра между вершинами $i$ и $j$ , мы можем определить $\mathrm {shortestPath} (i,j,k)$ в терминах следующей рекурсивной формулой:

базовый случай

\mathrm {shortestPath} (i,j,0)=w(i,j)

и рекурсивный случай

\mathrm {shortestPath} (i,j,k)=

\mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),

\mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}

.

Эта формула составляет основу алгоритма Флойда — Уоршелла. Алгоритм работает, сначала вычисляя $\mathrm {shortestPath} (i,j,k)$ для всех пар $(i,j)$ для $k=1$ , а затем $k=2$ , и так далее. Этот процесс продолжается до тех пор, пока $k=N$ не будет найден кратчайший путь для всех пар $(i,j)$ с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий:

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		1	2	3	4
k = 0		j
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


k = 1		1	2	3	4
k = 1		j
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


k = 2		1	2	3	4
k = 2		j
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0


k = 3		1	2	3	4
k = 3		j
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0


k = 4		1	2	3	4
k = 4		j
i	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

Поведение с отрицательными циклами

Отрицательный цикл — это цикл, сумма ребер которого равна отрицательному значению. Не существует кратчайшего пути между любой парой вершин $i$ , $j$ , которые являются частью отрицательного цикла, потому что длина пути от $i$ до $j$ может быть сколь угодно малой (отрицательный). Для численно значимого вывода, алгоритм Флойда — Уоршелла предполагает отсутствие отрицательных циклов. Тем не менее, если есть отрицательные циклы, то алгоритм Флойда — Уоршелла может быть использован для их обнаружения. Алгоритм обнаружения заключается в следующем:

Алгоритм Флойда — Уоршелла итеративно просматривает длину пути

между всеми парами вершин $(i,j)$ , включая те где $i=j$ ;

Изначально длина пути $(i,i)$ равна нулю;
Путь $[i,k,\ldots ,i]$ может улучшиться только в том случае, если его длина

меньше нуля, то есть обозначает отрицательный цикл;

Таким образом, после алгоритма, $(i,i)$ будет отрицательным, если

существует путь отрицательной длины от $i$ до $i$ .

Следовательно, чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда — Уоршелла, можно проверить диагональ матрицы кратчайших путей, и наличие отрицательного числа указывает на то, что граф содержит по крайней мере один отрицательный цикл. Во время выполнения алгоритма, если есть отрицательный цикл, могут появиться экспоненциально большие числа, вплоть до $\Omega (\cdot 6^{n-1}w_{max})$ , где $w_{max}$ — наибольшее абсолютное значение отрицательного ребра в графе. Чтобы избежать проблем переполнения/потери значимости, следует проверять наличие отрицательных чисел на диагонали матрицы кратчайших путей внутри внутреннего цикла «for» алгоритма. Очевидно, что в неориентированном графе отрицательное ребро создает отрицательный цикл (то есть замкнутый обход), включающий его инцидентные вершины. Если рассматривать все ребра приведенного выше примера графа как неориентированные, то видно, что, например, последовательность вершин 4 — 2 — 4 представляет собой цикл с весовой суммой -2.

Реконструкция путей

Алгоритм Флойда — Уоршелла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод восстановления фактического пути между любыми двумя вершинами конечной точки. Хотя кто-то может быть склонен хранить 3 фактический путь от каждой вершины к каждой другой вершине, это не обязательно, и на самом деле это очень дорого с точки зрения памяти. Вместо этого дерево кратчайших путей может быть вычислено для каждого узла за $\Theta (|E|)$ время, используя память $\Theta (|V|)$ для хранения каждого дерева, что позволяет нам эффективно реконструировать путь из любых двух связанных вершин.

Псевдокод^[1]

let dist be a  $|V|\times |V|$  массив минимальных расстояний, инициализированный как  $\infty$  (бесконечность)
let next be a  $|V|\times |V|$  массив индексов вершин, инициализированный 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

Анализ сложности Алгоритма

Пусть $n$ будет $|V|$ количеством вершин. Чтобы найти все $n^{2}$ из $\mathrm {shortestPath} (i,j,k)$ (для всех $i$ и $j$ ) из $\mathrm {shortestPath} (i,j,k-1)$ , требуется $2n^{2}$ операций. Поскольку мы начинаем с $\mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)$ и вычисляем последовательность $n$ матриц $\mathrm {shortestPath} (i,j,1)$ , $\mathrm {shortestPath} (i,j,2)$ , $\ldots$ , $\mathrm {shortestPath} (i,j,n)$ , общее количество используемых операций равно $n\cdot 2n^{2}=2n^{3}$ . Следовательно, сложность алгоритма равна $\Theta (n^{3})$ .

Приложения и обобщения

Алгоритм Флойда — Уоршелла может быть использован для решения следующих задач, в частности:

Кратчайшие пути в ориентированных графах (алгоритм Флойда)
Транзитивное замыкание ориентированных графов (алгоритм Уоршелла). В оригинальной формулировке алгоритма Уоршелла граф не взвешен и представлен булевой матрицей смежности. Затем операция сложения заменяется логической конъюнкцией (И), а минимальная операция — логической дизъюнкцией (ИЛИ).
Нахождение регулярного выражения, обозначающего регулярный язык, принимаемый конечным автоматом (алгоритм Клини, тесно связанное обобщение алгоритма Флойда — Уоршелла)
Обращение вещественных матриц (алгоритм Гаусса — Жордана)
Оптимальная маршрутизация. В этом приложении нужно найти путь с максимальным потоком между двумя вершинами. Это означает, что вместо взятия минимумов, как в псевдокоде выше, используются максимумы. Веса ребер представляют фиксированные ограничения для потока. Веса путей представляют собой узкие места поэтому операция сложения, указанная выше, заменяется минимальной операцией.
Быстрый расчет сетей 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

Сравнение с другими алгоритмами

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет $O(|V|\cdot |E|\log |V|)$ при применении двоичной кучи, что лучше, чем $O(|V|^{3})$ алгоритма Флойда — Уоршелла тогда, когда $|E|$ существенно меньше $|V|^{2}$ (условие разреженности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел)^[2]^[3]. Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда — Уоршелла проявляется только на больших графах.

Примечания

↑ Free Algorithms Book (неопр.). Дата обращения: 19 декабря 2020. Архивировано 12 января 2021 года.
↑ Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM, 49 (3): 289—317, doi:10.1145/567112.567114.
↑ Chan, Timothy M. (January 2010), "More algorithms for all-pairs shortest paths in weighted graphs", SIAM Journal on Computing, 39 (5): 2075—2089, doi:10.1137/08071990x.

Литература

Левитин А. В. Глава 11. Преодоление ограничений: Метод деления пополам // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 349—353. — 576 с. — ISBN 978-5-8459-0987-9
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.

[1] Free Algorithms Book (неопр.). Дата обращения: 19 декабря 2020. Архивировано 12 января 2021 года.

[2] Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM, 49 (3): 289—317, doi:10.1145/567112.567114.

[3] Chan, Timothy M. (January 2010), "More algorithms for all-pairs shortest paths in weighted graphs", SIAM Journal on Computing, 39 (5): 2075—2089, doi:10.1137/08071990x.

[1]

[2]

[3]

Алгоритмы поиска на графах
Неинформированные методы	Алгоритм Брона — Кербоша Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжёра