Алгоритм Флойда – Уоршалла

Алгоритм Флойда – Уоршалла
Сорт	Задача о кратчайшем пути для всех пар (для взвешенных графов)
Структура данных	График
Худшая производительность
Лучшая производительность
Средняя производительность
Наихудшая пространственная сложность

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

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

Алгоритм Флойда-Уоршалла является примером динамического программирования и был опубликован в его ныне признанной форме Робертом Флойдом в 1962 году. ^{[ 3 ]} Однако по сути это то же самое, что и алгоритмы, ранее опубликованные Бернаром Роем в 1959 году. ^{[ 4 ]} а также Стивеном Уоршаллом в 1962 году. ^{[ 5 ]} для нахождения транзитивного замыкания графа, ^{[ 6 ]} и тесно связан с алгоритмом Клини (опубликованным в 1956 году) для преобразования детерминированного конечного автомата в регулярное выражение . ^{[ 7 ]} Современная формулировка алгоритма в виде трех вложенных циклов for была впервые описана Питером Ингерманом также в 1962 году. ^{[ 8 ]}

Алгоритм

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

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

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

(1) путь из

i

к

k

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

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

, с последующим

(2) путь из

k

к

j

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

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

.

И, конечно же, это должен быть кратчайший такой путь (или несколько из них), иначе мы могли бы еще больше уменьшить длину. Другими словами, мы пришли к рекурсивной формуле:

\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,0)=w(i,j),

где $w(i,j)$ обозначает вес ребра из $i$ к $j$ если он существует, и ∞ (бесконечность) в противном случае.

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

Псевдокод

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (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$ с обновленными расстояниями, выделенными жирным шрифтом , будет следующей:


$к = 0$		1	2	3	4
$к = 0$		$дж$
$я$	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$к = 1$		1	2	3	4
$к = 1$		$дж$
$я$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$к = 2$		1	2	3	4
$к = 2$		$дж$
$я$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0


$к = 3$		1	2	3	4
$к = 3$		$дж$
$я$	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0


$к = 4$		1	2	3	4
$к = 4$		$дж$
$я$	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$ .

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

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

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

Псевдокод

Массив prev[u][v] содержит предпоследнюю вершину на пути из u к v (за исключением случаев prev[v][v], где он всегда содержит v даже если самопетли нет v): ^{[ 11 ]}

let dist be a  $|V|\times |V|$  array of minimum distances initialized to  $\infty$  (infinity)
let prev be a  $|V|\times |V|$  array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        prev[u][v] ← u
    for each vertex v do
        dist[v][v] ← 0
        prev[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        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]
                    prev[i][j] ← prev[k][j]

procedure Path(u, v) is
    if prev[u][v] = null then
        return []
    path ← [v]
    while u ≠ v do
        v ← prev[u][v]
        path.prepend(v)
    return path

Временная сложность

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

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

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

Кратчайшие пути в ориентированных графах (алгоритм Флойда).
Транзитивное замыкание ориентированных графов (алгоритм Уоршалла). В исходной формулировке алгоритма Уоршалла граф невзвешен и представлен булевой матрицей смежности . Тогда операция сложения заменяется логической конъюнкцией (И), а операция минимума — логической дизъюнкцией (ИЛИ).
Поиск регулярного выражения, обозначающего регулярный язык, принимаемый конечным автоматом ( алгоритм Клини , близкое обобщение алгоритма Флойда-Уоршалла) ^{[ 12 ]}
Обращение действительных алгоритм Гаусса – матриц ( Жордана ) ^{[ 13 ]}
Оптимальная маршрутизация. В этом приложении вас интересует поиск пути с максимальным потоком между двумя вершинами. Это означает, что вместо того, чтобы брать минимумы, как в приведенном выше псевдокоде, вместо этого берут максимумы. Веса ребер представляют собой фиксированные ограничения на поток. Веса путей представляют собой узкие места; поэтому описанная выше операция сложения заменяется операцией минимума.
Быстрое вычисление сетей Pathfinder .
Самые широкие пути/Пути с максимальной пропускной способностью
Вычисление канонической формы матриц разностных границ (DBM)
Вычисление сходства между графиками
Транзитивное замыкание в графах И/ИЛИ/порог. ^{[ 14 ]}

Реализации

Реализации доступны для многих языков программирования .

Для C++ в boost::graph библиотеке
Для C# в QuikGraph
Для C# : QuickGraphPCL (вилка QuickGraph с лучшей совместимостью с проектами, использующими переносимые библиотеки классов).
Для Java в Apache Commons Graph . библиотеке
Для JavaScript в Cytoscape . библиотеке
Для Юлии в Graphs.jl пакете
Для MATLAB в Matlab_bgl. пакете
Для Perl в Graph модуле
Для Python в библиотеке SciPy (модуль scipy.sparse.csgraph ) или NetworkX . библиотеке
Для R в пакетах e1071 и Rfast.

Сравнение с другими алгоритмами кратчайшего пути

Для графов с неотрицательными весами ребер алгоритм Дейкстры можно использовать для поиска всех кратчайших путей из одной вершины за время выполнения. $\Theta (|E|+|V|\log |V|)$ . Таким образом, запуск Дейкстры, начиная с каждой вершины, требует времени. $\Theta (|E||V|+|V|^{2}\log |V|)$ . С $|E|=O(|V|^{2})$ , это дает наихудшее время выполнения повторения Дейкстры $O(|V|^{3})$ . Хотя это соответствует асимптотическому времени работы алгоритма Флойда-Уоршалла в наихудшем случае, задействованные константы имеют весьма большое значение. Если граф плотный (т. $|E|\approx |V|^{2}$ ), алгоритм Флойда-Уоршалла на практике работает лучше. Когда граф разреженный (т. $|E|$ значительно меньше, чем $|V|^{2}$ ), Дейкстра имеет тенденцию доминировать.

Для разреженных графов с отрицательными ребрами, но без отрицательных циклов можно использовать алгоритм Джонсона с тем же асимптотическим временем работы, что и повторный подход Дейкстры.

Существуют также известные алгоритмы, использующие быстрое умножение матриц для ускорения вычисления кратчайшего пути для всех пар в плотных графах, но они обычно делают дополнительные предположения о весах ребер (например, требуют, чтобы они были небольшими целыми числами). ^{[ 15 ]}^{[ 16 ]} Кроме того, из-за высоких постоянных коэффициентов времени работы они обеспечивают ускорение по сравнению с алгоритмом Флойда-Уоршалла только для очень больших графов.

Ссылки

^ Jump up to: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 . См., в частности, раздел 26.2, «Алгоритм Флойда – Уоршалла», стр. 558–565 и раздел 26.4, «Общая основа решения задач о путях в ориентированных графах», стр. 570–576.
^ Кеннет Х. Розен (2003). Дискретная математика и ее приложения, 5-е издание . Эддисон Уэсли. ISBN 978-0-07-119881-3 .
^ Флойд, Роберт В. (июнь 1962 г.). «Алгоритм 97: Кратчайший путь» . Коммуникации АКМ . 5 (6): 345. дои : 10.1145/367766.368168 . S2CID 2003382 .
^ Рой, Бернард (1959). «Транзитивность и связность» . ЧР акад. наук. Париж (на французском языке). 249 : 216–218.
^ Уоршалл, Стивен (январь 1962 г.). «Теорема о булевых матрицах» . Журнал АКМ . 9 (1): 11–12. дои : 10.1145/321105.321107 . S2CID 33763989 .
^ Вайсштейн, Эрик В. «Алгоритм Флойда-Уоршалла» . Математический мир .
^ Клини, Южная Каролина (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Шеннон и Дж. Маккарти (ред.). Исследования автоматов . Издательство Принстонского университета. стр. 3–42.
^ Ингерман, Питер З. (ноябрь 1962 г.). «Алгоритм 141: Матрица путей» . Коммуникации АКМ . 5 (11): 556. дои : 10.1145/368996.369016 . S2CID 29010500 .
^ Jump up to: ^а ^б Хохбаум, Дорит (2014). «Раздел 8.9: Алгоритм Флойда-Уоршалла для всех пар кратчайших путей» (PDF) . Конспект лекций для IEOR 266: Алгоритмы графов и сетевые потоки . Департамент промышленной инженерии и исследований операций Калифорнийского университета в Беркли . стр. 41–42.
^ Стефан Хугарди (апрель 2010 г.). «Алгоритм Флойда – Уоршалла на графах с отрицательными циклами». Письма об обработке информации . 110 (8–9): 279–281. дои : 10.1016/j.ipl.2010.02.001 .
^ «Бесплатная книга алгоритмов» .
^ Гросс, Джонатан Л.; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204 .
^ Пеналоса, Рафаэль. «Алгебраические структуры для транзитивного замыкания». CiteSeerX 10.1.1.71.7650 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Гиллис, Дональд (1993). Планирование задач с ограничениями приоритета И/ИЛИ (кандидатская диссертация, Приложение B) (PDF) (Отчет).
^ Цвик, Ури (май 2002 г.), «Кратчайшие пути для всех пар с использованием наборов мостов и умножения прямоугольных матриц», Journal of the ACM , 49 (3): 289–317, arXiv : cs/0008011 , doi : 10.1145/567112.567114 , S2CID 1065901 .
^ Чан, Тимоти М. (январь 2010 г.), «Дополнительные алгоритмы для кратчайших путей для всех пар во взвешенных графах», SIAM Journal on Computing , 39 (5): 2075–2089, CiteSeerX 10.1.1.153.6864 , doi : 10.1137/08071990x .

Внешние ссылки

[:0-1] Jump up to: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 . См., в частности, раздел 26.2, «Алгоритм Флойда – Уоршалла», стр. 558–565 и раздел 26.4, «Общая основа решения задач о путях в ориентированных графах», стр. 570–576.

[2] Кеннет Х. Розен (2003). Дискретная математика и ее приложения, 5-е издание . Эддисон Уэсли. ISBN 978-0-07-119881-3 .

[3] Флойд, Роберт В. (июнь 1962 г.). «Алгоритм 97: Кратчайший путь» . Коммуникации АКМ . 5 (6): 345. дои : 10.1145/367766.368168 . S2CID 2003382 .

[4] Рой, Бернард (1959). «Транзитивность и связность» . ЧР акад. наук. Париж (на французском языке). 249 : 216–218.

[5] Уоршалл, Стивен (январь 1962 г.). «Теорема о булевых матрицах» . Журнал АКМ . 9 (1): 11–12. дои : 10.1145/321105.321107 . S2CID 33763989 .

[6] Вайсштейн, Эрик В. «Алгоритм Флойда-Уоршалла» . Математический мир .

[7] Клини, Южная Каролина (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Шеннон и Дж. Маккарти (ред.). Исследования автоматов . Издательство Принстонского университета. стр. 3–42.

[8] Ингерман, Питер З. (ноябрь 1962 г.). «Алгоритм 141: Матрица путей» . Коммуникации АКМ . 5 (11): 556. дои : 10.1145/368996.369016 . S2CID 29010500 .

[:1-9] Jump up to: ^а ^б Хохбаум, Дорит (2014). «Раздел 8.9: Алгоритм Флойда-Уоршалла для всех пар кратчайших путей» (PDF) . Конспект лекций для IEOR 266: Алгоритмы графов и сетевые потоки . Департамент промышленной инженерии и исследований операций Калифорнийского университета в Беркли . стр. 41–42.

[10] Стефан Хугарди (апрель 2010 г.). «Алгоритм Флойда – Уоршалла на графах с отрицательными циклами». Письма об обработке информации . 110 (8–9): 279–281. дои : 10.1016/j.ipl.2010.02.001 .

[11] «Бесплатная книга алгоритмов» .

[12] Гросс, Джонатан Л.; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204 .

[13] Пеналоса, Рафаэль. «Алгебраические структуры для транзитивного замыкания». CiteSeerX 10.1.1.71.7650 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[14] Гиллис, Дональд (1993). Планирование задач с ограничениями приоритета И/ИЛИ (кандидатская диссертация, Приложение B) (PDF) (Отчет).

[15] Цвик, Ури (май 2002 г.), «Кратчайшие пути для всех пар с использованием наборов мостов и умножения прямоугольных матриц», Journal of the ACM , 49 (3): 289–317, arXiv : cs/0008011 , doi : 10.1145/567112.567114 , S2CID 1065901 .

[16] Чан, Тимоти М. (январь 2010 г.), «Дополнительные алгоритмы для кратчайших путей для всех пар во взвешенных графах», SIAM Journal on Computing , 39 (5): 2075–2089, CiteSeerX 10.1.1.153.6864 , doi : 10.1137/08071990x .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

v т и графов и деревьев Алгоритмы обхода
Search	α–β pruning A* IDA* LPA* SMA* Best-first search Beam search Bidirectional search Breadth-first search Lexicographic Parallel B* Depth-first search Iterative deepening D* Fringe search Jump point search Monte Carlo tree search SSS*
Shortest path	Bellman–Ford Dijkstra's Floyd–Warshall Johnson's Shortest path faster Yen's
Minimum spanning tree	Borůvka's Kruskal's Prim's Reverse-delete
List of graph search algorithms