Алгоритм Флойда-Уоршолла - Floyd–Warshall algorithm

«Алгоритм Флойда» перенаправляется сюда. Для обнаружения цикла см. Алгоритм поиска цикла Флойда. Для компьютерной графики см. Дизеринг Флойда – Стейнберга.

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

Учебный класс	Задача о кратчайшем пути для всех пар (для взвешенных графиков)
Структура данных	График
Худший случай спектакль	${\displaystyle \Theta (|V|^{3})}$
Лучший случай спектакль	${\displaystyle \Theta (|V|^{3})}$
Средний спектакль	${\displaystyle \Theta (|V|^{3})}$
Худший случай космическая сложность	${\displaystyle \Theta (|V|^{2})}$

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

История и нейминг

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

Алгоритм

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

Рассмотрим график ${\displaystyle G}$ с вершинами ${\displaystyle V}$ пронумерованные от 1 до${\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,k)}$ может быть либо

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

или же

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

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

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

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

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

${\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,k)}$ для всех ${\displaystyle (i,j)}$ пары для ${\displaystyle k=1}$, тогда ${\displaystyle k=2}$, и так далее. Этот процесс продолжается до тех пор, пока ${\displaystyle k=N}$, и мы нашли кратчайший путь для всех ${\displaystyle (i,j)}$ пары с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий:^{[оригинальное исследование? ]}

позволять dist be a | V | × | V | массив минимальных расстояний, инициализированный как ∞ (бесконечность)для каждого край (ты, v) делать    dist [ты][v] ← w (ты, v)  // Вес края (ты, v)для каждого вершина v делать    dist [v][v] ← 0за k из 1 к | V | за я из 1 к | V | за j из 1 к | V | если dist [я][j]> dist [я][k] + dist [k][j] dist [я][j] ← dist [я][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, с обновленными расстояниями в смелый, будет:

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

k = 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

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

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

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

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

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

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

процедура Путь (u, v) если следующий [u] [v] = ноль тогда        возвращаться [] путь = [u] пока ты ≠ v        u ← далее [u] [v] path.append (u) возвращаться дорожка

Анализ

Позволять ${\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]
• Оптимальная маршрутизация. В этом приложении нужно найти путь с максимальным потоком между двумя вершинами. Это означает, что вместо того, чтобы брать минимумы, как в псевдокоде выше, вместо этого используются максимумы. Веса ребер представляют фиксированные ограничения для потока. Веса путей представляют собой узкие места; поэтому операция сложения, указанная выше, заменяется минимальной операцией.
• Быстрое вычисление Сети следопытов.
• Самые широкие пути / пути с максимальной пропускной способностью
• Вычисление канонической формы матриц разностных границ (DBM)
• Вычисление сходства между графами

Реализации

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

• За C ++, в boost :: graph библиотека
• За C #, в QuickGraph
• За C #, в QuickGraphPCL (Ответвление QuickGraph с лучшей совместимостью с проектами, использующими переносимые библиотеки классов.)
• За Ява, в График Apache Commons библиотека
• За JavaScript, в Cytoscape библиотека
• За MATLAB, в Matlab_bgl упаковка
• За Perl, в График модуль
• За Python, в SciPy библиотека (модуль scipy.sparse.csgraph ) или же NetworkX библиотека
• За р, в пакетах e1071 и Rfast

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

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

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

Рекомендации

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. Дои:10.1145/367766.368168.
4. Рой, Бернард (1959). "Transitivité et connexité". C. R. Acad. Sci. Париж (На французском). 249: 216–218.
5. Уоршолл, Стивен (январь 1962 г.). «Теорема о булевых матрицах». Журнал ACM. 9 (1): 11–12. Дои:10.1145/321105.321107.
6. Вайсштейн, Эрик В. «Алгоритм Флойда-Уоршалла». MathWorld.
7. Клини, С. (1956). «Представление событий в нервных сетях и конечных автоматах». В К. Э. Шеннон и Дж. Маккарти (ред.). Исследования автоматов. Издательство Принстонского университета. С. 3–42.
8. Ингерман, Петр З. (ноябрь 1962 г.). «Алгоритм 141: Матрица путей». Коммуникации ACM. 5 (11): 556. Дои:10.1145/368996.369016.
9. Хохбаум, Дорит (2014). «Раздел 8.9: Алгоритм Флойда-Уоршалла для всех пар кратчайших путей» (PDF ). Лекционные заметки для IEOR 266: алгоритмы графов и сетевые потоки. Департамент промышленной инженерии и операционных исследований, Калифорнийский университет в Беркли.
10. Стефан Хугарди (апрель 2010 г.). «Алгоритм Флойда – Уоршалла на графах с отрицательными циклами». Письма об обработке информации. 110 (8–9): 279–281. Дои:10.1016 / j.ipl.2010.02.001.
11. https://books.goalkicker.com/AlgorithmsBook/
12. Гросс, Джонатан Л .; Йеллен, Джей (2003), Справочник по теории графов, Дискретная математика и ее приложения, CRC Press, стр. 65, ISBN  9780203490204.
13. Пеналоза, Рафаэль. «Алгебраические структуры для транзитивного замыкания». CiteSeerX  10.1.1.71.7650.
14. Цвик, Ури (Май 2002 г.), «Все пары кратчайших путей с использованием наборов мостов и умножения прямоугольных матриц», Журнал ACM, 49 (3): 289–317, arXiv:cs / 0008011, Дои:10.1145/567112.567114.
15. Чан, Тимоти М. (Январь 2010 г.), «Дополнительные алгоритмы для кратчайших путей для всех пар во взвешенных графах», SIAM Журнал по вычислениям, 39 (5): 2075–2089, CiteSeerX  10.1.1.153.6864, Дои:10.1137 / 08071990x.

внешняя ссылка

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