В информатике , то Флойд-Воршалл алгоритм (также известный как алгоритм Флойд , то Рой-Воршалл алгоритм , то алгоритм Рой-Флойд , или алгоритм ВДИ ) представляет собой алгоритм для нахождения кратчайших путей в ориентированном взвешенном графе с положительным или отрицательным краем веса (но без отрицательных циклов). [1] [2]Одно выполнение алгоритма найдет длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает подробную информацию о самих путях, их можно восстановить с помощью простых модификаций алгоритма. Варианты алгоритма также могут быть использованы для нахождения транзитивного замыкания отношения, или (в связи с системой голосования Шульце ) широчайшие пути между всеми парами вершин взвешенного графа.
Класс | Задача поиска кратчайшего пути для всех пар (для взвешенных графов) |
---|---|
Структура данных | График |
Наихудшая производительность | |
Лучшая производительность | |
Средняя производительность | |
Сложность пространства в наихудшем случае |
История и нейминг
Алгоритм Флойда-Уоршалла является примером динамического программирования и был опубликован в его признанной в настоящее время форме Робертом Флойдом в 1962 году. [3] Однако по сути он аналогичен алгоритмам, ранее опубликованным Бернардом Роем в 1959 году [4], а также от Стивена Воршалла в 1962 году [5] для нахождения транзитивного замыкания графа, [6] и тесно связан с алгоритмом Клини (опубликовано в 1956) для преобразования детерминированного конечного автомата в регулярное выражение . [7] Современная формулировка алгоритма в виде трех вложенных циклов for была впервые описана Питером Ингерманом также в 1962 году. [8]
Алгоритм
Алгоритм Флойда – Уоршалла сравнивает все возможные пути через граф между каждой парой вершин. Это можно сделать с помощью сравнений на графике, даже если там может быть до ребер в графе, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.
Рассмотрим график с вершинами пронумерованные от 1 до . Далее рассмотрим функцию который возвращает кратчайший путь из к используя вершины только из множества как промежуточные точки по пути. Теперь, учитывая эту функцию, наша цель - найти кратчайший путь из каждого для каждого используя любую вершину в.
Для каждой из этих пар вершин может быть либо
- (1) путь, который не проходит (использует только вершины из набора .)
или же
- (2) путь, который действительно проходит (из к а затем из к , оба используют только промежуточные вершины в )
Мы знаем, что лучший путь от к который использует только вершины через определяется , и ясно, что если бы был лучший путь от к к , то длина этого пути будет объединением кратчайшего пути из к (только с использованием промежуточных вершин в ) и кратчайший путь из к (только с использованием промежуточных вершин в ).
Если вес ребра между вершинами а также , мы можем определить в терминах следующей рекурсивной формулы: базовый случай
и рекурсивный случай
- .
Эта формула является сердцем алгоритма Флойда – Уоршалла. Алгоритм работает путем первых вычислений для всех пары для , тогда , и так далее. Этот процесс продолжается до тех пор, пока, и мы нашли кратчайший путь для всех пары с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий: [ оригинальное исследование? ]
пусть dist будет a | 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 | если 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 , обновленные расстояния выделены жирным шрифтом , будет иметь вид:
к = 0 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
я | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 3 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | ∞ | −1 | ∞ | 0 |
k = 1 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
я | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 2 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | ∞ | −1 | ∞ | 0 |
k = 2 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
я | 1 | 0 | ∞ | −2 | ∞ |
2 | 4 | 0 | 2 | ∞ | |
3 | ∞ | ∞ | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
k = 3 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
я | 1 | 0 | ∞ | −2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | ∞ | ∞ | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
к = 4 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
я | 1 | 0 | −1 | −2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | 5 | 1 | 0 | 2 | |
4 | 3 | −1 | 1 | 0 |
Поведение с отрицательными циклами
Отрицательный цикл - это цикл, сумма граней которого равна отрицательному значению. Между любой парой вершин нет кратчайшего пути, которые образуют часть отрицательного цикла, потому что длины пути от к может быть сколь угодно малым (отрицательным). Для численно значимого вывода алгоритм Флойда – Уоршалла предполагает отсутствие отрицательных циклов. Тем не менее, если есть отрицательные циклы, алгоритм Флойда – Уоршалла может быть использован для их обнаружения. Интуиция такая:
- Алгоритм Флойда – Уоршалла итеративно пересматривает длины путей между всеми парами вершин. , в том числе где ;
- Изначально длина пути равно нулю;
- Путь может только улучшить это, если он имеет длину меньше нуля, то есть обозначает отрицательный цикл;
- Таким образом, после алгоритма будет отрицательным, если существует путь отрицательной длины от вернуться к .
Следовательно, чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда – Уоршалла, можно проверить диагональ матрицы путей, и наличие отрицательного числа указывает на то, что граф содержит по крайней мере один отрицательный цикл. [9] Во время выполнения алгоритма, если есть отрицательный цикл, могут появиться экспоненциально большие числа, вплоть до, где - наибольшее абсолютное значение отрицательного ребра в графе. Чтобы избежать проблем переполнения / потери значимости, следует проверять наличие отрицательных чисел на диагонали матрицы путей во внутреннем цикле for алгоритма. [10] Очевидно, что в неориентированном графе отрицательное ребро создает отрицательный цикл (т. Е. Замкнутый обход), включающий его инцидентные вершины. Рассматривая все ребра приведенного выше примера графа как неориентированные, например, последовательность вершин 4–2–4 является циклом с весовой суммой −2.
Реконструкция пути
Алгоритм Флойда – Уоршалла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод для восстановления фактического пути между любыми двумя вершинами конечной точки. Хотя кто-то может быть склонен хранить фактический путь от каждой вершины к другой вершине, в этом нет необходимости, и на самом деле это очень дорого с точки зрения памяти. Вместо этого дерево кратчайших путей может быть вычислено для каждого узла в время используя память для хранения каждого дерева, что позволяет нам эффективно восстанавливать путь из любых двух связанных вершин.
Псевдокод [11]
пусть dist будет массив минимальных расстояний, инициализированный (бесконечность) пусть следующий будет массив индексов вершин, инициализированный нулемПроцедура FloydWarshallWithPathReconstruction () является для каждого ребра (U, V) сделать DIST [и] [V] ← ш (U, V) // Вес ребра (U, V) следующий [u] [v] ← v для каждой вершины v сделать расст [v] [v] ← 0 следующая [v] [v] ← v для k от 1 до | V | do // стандартная реализация Флойда-Уоршалла для 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] ← следующая [i] [k]
процедура Path (u, v) если next [u] [v] = null, то return [] путь = [u] в то время как u ≠ v u ← далее [u] [v] path.append (u) обратный путь
Анализ
Позволять быть , количество вершин. Найти все из (для всех а также ) из требует операции. Поскольку мы начинаем с и вычислим последовательность матрицы , , , , общее количество использованных операций равно . Следовательно, сложность алгоритма равна.
Приложения и обобщения
Алгоритм Флойда-Уоршалла может использоваться, среди прочего, для решения следующих задач:
- Кратчайшие пути в ориентированных графах (алгоритм Флойда).
- Транзитивное замыкание ориентированных графов (алгоритм Уоршалла). В оригинальной формулировке алгоритма Уоршалла граф невзвешен и представлен булевой матрицей смежности . Затем операция сложения заменяется логическим соединением (И), а минимальная операция - логическим дизъюнкцией (ИЛИ).
- Нахождение регулярного выражения, обозначающего регулярный язык, принимаемый конечным автоматом ( алгоритм Клини , тесно связанное обобщение алгоритма Флойда – Уоршалла) [12]
- Инверсия из реальных матриц ( Гаусс-Жордан алгоритм ) [13]
- Оптимальная маршрутизация. В этом приложении нужно найти путь с максимальным потоком между двумя вершинами. Это означает, что вместо взятия минимумов, как в псевдокоде выше, используются максимумы. Веса ребер представляют фиксированные ограничения потока. Веса путей представляют собой узкие места; поэтому операция сложения, указанная выше, заменяется минимальной операцией.
- Быстрое вычисление сетей Pathfinder .
- Самые широкие пути / пути с максимальной пропускной способностью
- Вычисление канонической формы матриц разностных границ (DBM)
- Вычисление сходства между графами
- Транзитивное замыкание в графах И / ИЛИ / пороговых значений. [14]
Реализации
Реализации доступны для многих языков программирования .
- Для 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
Сравнение с другими алгоритмами кратчайшего пути
Алгоритм Флойда – Уоршалла - хороший выбор для вычисления путей между всеми парами вершин в плотных графах , в которых большинство или все пары вершин соединены ребрами. Для разреженных графов с неотрицательными весами ребер меньшая асимптотическая сложность может быть получена путем запуска алгоритма Дейкстры из каждой возможной начальной вершины, поскольку наихудшее время работы повторяющегося Дейкстры (с использованием кучи Фибоначчи ) меньше, чем время работы алгоритма Флойда – Уоршалла, когда значительно меньше, чем . Для разреженных графов с отрицательными ребрами, но без отрицательных циклов можно использовать алгоритм Джонсона с тем же асимптотическим временем выполнения, что и при повторном подходе Дейкстры.
Также известны алгоритмы, использующие быстрое умножение матриц для ускорения вычисления кратчайшего пути для всех пар в плотных графах, но они обычно делают дополнительные предположения о весах ребер (например, требуют, чтобы они были маленькими целыми числами). [15] [16] Кроме того, из-за высоких постоянных факторов во времени их работы они могут обеспечить ускорение по сравнению с алгоритмом Флойда – Уоршалла только для очень больших графов.
Рекомендации
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (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: кратчайший путь». Коммуникации ACM . 5 (6): 345. DOI : 10,1145 / 367766,368168 .
- ^ Рой, Бернард (1959). "Transitivité et connexité" . CR Acad. Sci. Париж (на французском). 249 : 216–218.
- ^ Уоршолл, Стивен (январь 1962 г.). «Теорема о булевых матрицах». Журнал ACM . 9 (1): 11–12. DOI : 10.1145 / 321105.321107 .
- ^ Вайсштейн, Эрик В. "Алгоритм Флойда-Уоршалла" . MathWorld .
- ^ Клини, SC (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Шеннон и Дж. Маккарти (ред.). Исследования автоматов . Издательство Принстонского университета. С. 3–42.
- ^ Ингерман, Петр З. (ноябрь 1962 г.). «Алгоритм 141: Матрица путей». Коммуникации ACM . 5 (11): 556. DOI : 10,1145 / 368996,369016 .
- ^ Хохбаум, Дорит (2014). «Раздел 8.9: Алгоритм Флойда-Уоршалла для всех пар кратчайших путей» ( PDF ) . Лекционные заметки для IEOR 266: алгоритмы графов и сетевые потоки . Департамент промышленной инженерии и исследования операций Калифорнийского университета в Беркли .
- ^ Стефан Хугарди (апрель 2010 г.). «Алгоритм Флойда – Уоршолла на графах с отрицательными циклами». Письма об обработке информации . 110 (8–9): 279–281. DOI : 10.1016 / j.ipl.2010.02.001 .
- ^ https://books.goalkicker.com/AlgorithmsBook/
- ^ Гросс, Джонатан Л .; Йеллен, Джей (2003), Справочник по теории графов , дискретной математике и ее приложениям, CRC Press, стр. 65, ISBN 9780203490204.
- ^ Пеналоза, Рафаэль. «Алгебраические структуры для транзитивного замыкания». CiteSeerX 10.1.1.71.7650 . Цитировать журнал требует
|journal=
( помощь ) - ^ Гиллис, Дональд (1993). Планирование задач с ограничениями приоритета И / ИЛИ (докторская диссертация, приложение B) (PDF) (отчет).
- ^ Цвик, Ури (май 2002 г.), «Все пары кратчайших путей с использованием наборов мостов и умножения прямоугольных матриц», Журнал ACM , 49 (3): 289–317, arXiv : cs / 0008011 , doi : 10.1145 / 567112.567114.
- ^ Чан, Тимоти М. (январь 2010 г.), «Дополнительные алгоритмы для кратчайших путей для всех пар во взвешенных графах», SIAM Journal on Computing , 39 (5): 2075–2089, CiteSeerX 10.1.1.153.6864 , doi : 10.1137 / 08071990x.
Внешние ссылки
- Интерактивная анимация алгоритма Флойда – Уоршалла.
- Интерактивная анимация алгоритма Флойда – Уоршалла (Мюнхенский технический университет)