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

Алгоритм поиска кратчайших путей для всех пар в графах, позволяющий сделать веса некоторых ребер отрицательными.

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

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

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

Алгоритм

Алгоритм Флойда-Уоршалла сравнивает множество возможных путей в графе между каждой парой вершин. Он гарантированно находит все кратчайшие пути и может делать это с помощью сравнений в графе, даже если в графе могут быть ребра. Это делается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной. ${\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| × |В| массив минимальных расстояний, инициализированный значением ∞ (бесконечность) для каждого ребра ( 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| если 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 с обновленными расстояниями, выделенными жирным шрифтом , будет следующей:

Поведение при негативных циклах

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

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

Алгоритм Флойда-Уоршалла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод для восстановления фактического пути между любыми двумя конечными вершинами. Хотя можно сохранить действительный путь от каждой вершины к другой вершине, в этом нет необходимости и, по сути, очень затратно с точки зрения памяти. Вместо этого дерево кратчайшего пути может быть рассчитано для каждого узла во времени, используя память для хранения каждого дерева, что позволяет нам эффективно восстанавливать путь из любых двух связанных вершин. ${\displaystyle \Theta (|E|)}$ ${\displaystyle \Theta (|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] ← ты для каждой вершины v делаем dist[v][v] ← 0 предыдущая[v][v] ← v для k от 1 до |V| do  // стандартная реализация Floyd-Warshall  для i от 1 до |V| для j от 1 до |V| если dist[i][j] > dist[i][k] + dist[k][j], то dist[i][j] ← dist[i][k] + dist[k][j] предыдущая[i][j] ← предыдущая[k][j]

процедура Path(u, v) , если prev[u][v] = null, то  вернуть [] путь ← [v] пока  ты ≠ 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 2n^{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 n\cdot 2n^{2}=2n^{3}}$ ${\displaystyle \Theta (n^{3})}$

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

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

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

Реализации

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

• Для C++ в библиотеке boost::graph
• Для C# в QuickGraph
• Для 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: Кратчайший путь». Коммуникации АКМ . 5 (6): 345. дои : 10.1145/367766.368168 . S2CID  2003382.
4. Рой, Бернард (1959). «Transitivité et connexité». ЧР акад. наук. Париж (на французском языке). 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.
9. Хохбаум, Дорит (2014). «Раздел 8.9: Алгоритм Флойда-Уоршалла для всех пар кратчайших путей» (PDF) . Конспект лекций для IEOR 266: Алгоритмы графов и сетевые потоки . Департамент промышленной инженерии и исследований операций Калифорнийского университета в Беркли .
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 .

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

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