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

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

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

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

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

Алгоритм

Алгоритм Floyd -Warshall сравнивает многие возможные пути через график между каждой парой вершин. Это гарантированно найдет все кратчайшие пути и может сделать это с $\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$ с обновленными расстояниями в жирном шрифте будет:


$k = 0$		1	2	3	4
$k = 0$		$Дж$
$я$	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$k = 1$		1	2	3	4
$k = 1$		$Дж$
$я$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$k = 2$		1	2	3	4
$k = 2$		$Дж$
$я$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0


$k = 3$		1	2	3	4
$k = 3$		$Дж$
$я$	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0


$k = 4$		1	2	3	4
$k = 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.

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

Алгоритм Floyd -Warshall обычно обеспечивает только длины пути между всеми парами вершин. При простых модификациях можно создать метод для восстановления фактического пути между любыми двумя вершинами конечной точки. В то время как человек может быть склонен хранить фактический путь от каждой вершины друг к другу в вершину, это не обязательно, и на самом деле очень дорого с точки зрения памяти. Вместо этого мы можем использовать дерево с кратчайшей дорожкой , которое можно рассчитать для каждого узла в $\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})$ .

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

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

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

Реализации

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

Для C ++ , в Graph Boost :: библиотеке
Для C# , в Quikgraph
Для C# , в QuickGraphpcl (вилка QuickGraph с лучшей совместимостью с проектами с использованием портативных классовых библиотек.)
Для Java , в графика Apache Commons библиотеке
Для JavaScript , в цитоскапов библиотеке
Для Джулии , в Graphs.jl пакете
Для Matlab , в MATLAB_BGL пакете
Для Perl , в графическом модуле
Для Python , в библиотеке Scipy (модуль scipy.sparse.csgraph ) или Networkx библиотека
Для R , в пакетах e1071 и rfast

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

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

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

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

Ссылки

^ Jump up to: ^а ^{беременный} Корммен, Томас Х .; , Чарльз Э. Лейзерон Ривест, Рональд Л. (1990). Введение в алгоритмы (1 -е изд.). С прессой и МакГроу-Хилл. 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 . S2CID 2003382 .
^ Рой, Бернард (1959). «Транзитивность и связь» . CR Acad. Наука Париж (по -французски). 249 : 216–218.
^ Warshall, Стивен (январь 1962 г.). «Теорема о логических матрицах» . Журнал ACM . 9 (1): 11–12. doi : 10.1145/321105.321107 . S2CID 33763989 .
^ Вейсштейн, Эрик У. "Алгоритм Флойд-Варшалла" . MathWorld .
^ Kleene, SC (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Shannon и J. McCarthy (Ed.). Автоматы исследования . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА. С. 3–42.
^ Ингерман, Питер З. (ноябрь 1962). «Алгоритм 141: матрица пути» . Коммуникации ACM . 5 (11): 556. doi : 10.1145/368996.369016 . S2CID 29010500 .
^ Jump up to: ^а ^{беременный} Hochbaum, Dorit (2014). «Раздел 8.9: Алгоритм Флойд-Варшалла для всех паров самых коротких путей» (PDF) . Примечания лекции для IEOR 266: Алгоритмы графика и сетевые потоки . Департамент промышленной инженерии и исследований операций, Калифорнийский университет, Беркли . С. 41–42.
^ Стефан Хогарди (апрель 2010 г.). «Алгоритм Флойда -Варшалла на графиках с отрицательными циклами». Информационная обработка букв . 110 (8–9): 279–281. doi : 10.1016/j.ipl.2010.02.001 .
^ «Бесплатные алгоритмы книги» .
^ Гросс, Джонатан Л.; Йеллен, Джей (2003), Справочник по теории графика , дискретной математике и ее приложения, CRC Press, p. 65, ISBN 9780203490204 .
^ Пеналоза, Рафаэль. «Алгебраические структуры для переходного закрытия». Citeseerx 10.1.1.71.7650 . {{cite journal}}: CITE Journal требует |journal= ( помощь )
^ Джиллис, Дональд (1993). Задачи планирования с и/или приоритетными противоречатами (кандидатская диссертация, Приложение B) (PDF) (отчет).
^ Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM , 49 (3): 289–317, arXiv : cs/0008011 , doi : 10.1145/567112.567114 , S2CID 1065901 Полем
^ Chan, Timothy M. (январь 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 -е изд.). С прессой и МакГроу-Хилл. 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). «Транзитивность и связь» . CR Acad. Наука Париж (по -французски). 249 : 216–218.

[5] Warshall, Стивен (январь 1962 г.). «Теорема о логических матрицах» . Журнал ACM . 9 (1): 11–12. doi : 10.1145/321105.321107 . S2CID 33763989 .

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

[7] Kleene, SC (1956). «Представление событий в нервных сетях и конечных автоматах». В CE Shannon и J. McCarthy (Ed.). Автоматы исследования . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА. С. 3–42.

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

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

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

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

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

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

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

[15] Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM , 49 (3): 289–317, arXiv : cs/0008011 , doi : 10.1145/567112.567114 , S2CID 1065901 Полем

[16] Chan, Timothy M. (январь 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 Т и графика и деревьев Алгоритмы обхода
Поиск	А -b обрезка A* ИДА* LPA* SMA* Лучший поиск Лучший поиск ДИВКАЛЬНЫЙ ПОИСК Поиск по ширине Лексикография Параллель Б* Глубина-первый поиск Итеративное углубление D* Fringe Search Поиск точки прыжка Поиск дерева Монте -Карло SSS*
Кратчайший путь	Беллман - Форд Дейкстра Флойд-Варшалл Джонсон Краткий путь быстрее Иена
Минимальное охвативное дерево	Черника Крускал Прим Обратный отбор
Список алгоритмов поиска графика