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

Алгоритм в теории графов

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

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

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

Алгоритм

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

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

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

(1) путь от до , который использует вершины , за которым следует ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle \{1,2,\ldots ,k-1\}}$

(2) путь от до , использующий вершины . ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle \{1,2,\ldots ,k-1\}}$

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

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

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

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

Базовый вариант определяется как

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

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

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

Псевдокод

пусть dist будет массивом минимальных расстояний размером |V| × |V|, инициализированным значением ∞ (бесконечность) для каждого ребра ( u , v ) do dist[ u ][ v ] ← w( u , v ) // Вес ребра ( u , v ) для каждой вершины v  do dist[ v ][ v ] ← 0 для  k  от 1 до |V| для  i  от 1 до |V| для  j  от 1 до |V| if dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ] конец если

Пример

Приведенный выше алгоритм реализован на графике слева ниже:

До первой рекурсии внешнего цикла, обозначенного выше как 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 , где обновленные расстояния выделены жирным шрифтом , будет иметь вид:

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

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

• Алгоритм Флойда–Уоршелла итеративно пересматривает длины путей между всеми парами вершин , включая , где ; ${\displaystyle (i,j)}$ ${\displaystyle i=j}$
• Первоначально длина пути равна нулю; ${\displaystyle (i,i)}$
• Путь может улучшить это значение только в том случае, если его длина меньше нуля, т.е. он обозначает отрицательный цикл; ${\displaystyle [i,k,\ldots ,i]}$
• Таким образом, после алгоритма будет отрицательным, если существует путь отрицательной длины от обратно до . ${\displaystyle (i,i)}$ ${\displaystyle i}$ ${\displaystyle i}$

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

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

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

Псевдокод

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

пусть dist будет массивом минимальных расстояний, инициализированным (бесконечностью) , пусть prev будет массивом индексов вершин, инициализированным значением null ${\displaystyle |V|\times |V|}$ ${\displaystyle \infty }$ ${\displaystyle |V|\times |V|}$процедура  FloydWarshallWithPathReconstruction () для  каждого ребра (u, v) do dist[u][v] ← w(u, v) // Вес ребра (u, v) предыдущая[u][v] ← u для каждой вершины v сделать расст[v][v] ← 0 предыдущая[v][v] ← v для k от 1 до |V| do  // стандартная реализация Флойда-Уоршелла  для i от 1 до |V| для j от 1 до |V| if dist[i][j] > dist[i][k] + dist[k][j] then расстояние[i][j] ← расстояние[i][k] + расстояние[k][j] предыдущая[i][j] ← предыдущая[k][j]

Процедура  Path (u, v) —  если prev[u][v] = null , то  возвращается [] путь ← [v] пока  u ≠ v  делать v ← предыдущая[u][v] путь.prepend(v) обратный путь

Сложность времени

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

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

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

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

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

Ссылки

1. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (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: Кратчайший путь». Сообщения ACM . 5 (6): 345. doi : 10.1145/367766.368168 . S2CID  2003382.
4. Рой, Бернард (1959). «Transitivité et connexité». ЧР акад. наук. Париж (на французском языке). 249 : 216–218.
5. Уоршалл, Стивен (январь 1962 г.). «Теорема о булевых матрицах». Журнал ACM . 9 (1): 11–12. doi : 10.1145/321105.321107 . S2CID  33763989.
6. Вайсштейн, Эрик В. «Алгоритм Флойда-Уоршелла». MathWorld .
7. Клини, SC (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Shannon и J. McCarthy (ред.). Automata Studies . Princeton University Press. стр. 3–42.
8. Ингерман, Питер З. (ноябрь 1962 г.). «Алгоритм 141: Матрица путей». Сообщения ACM . 5 (11): 556. doi : 10.1145/368996.369016 . S2CID  29010500.
9. Hochbaum, Dorit (2014). "Раздел 8.9: Алгоритм Флойда-Уоршелла для всех пар кратчайших путей" (PDF) . Заметки к лекциям для IEOR 266: Графовые алгоритмы и сетевые потоки . Кафедра промышленной инженерии и исследования операций, Калифорнийский университет в Беркли . стр. 41–42.
10. Стефан Хугарди (апрель 2010 г.). «Алгоритм Флойда–Уоршелла на графах с отрицательными циклами». Information Processing Letters . 110 (8–9): 279–281. doi :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 г.), «Все пары кратчайших путей с использованием мостовых множеств и умножения прямоугольных матриц», Журнал 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 .

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

• Интерактивная анимация алгоритма Флойда–Уоршелла
• Интерактивная анимация алгоритма Флойда–Уоршелла (Технический университет Мюнхена)