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

---

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

Алгоритм Флойда — Уоршелла является примером динамического программирования и был опубликован в своей ныне признанной форме Робертом Флойдом в 1962 году. Однако он по сути такой же, как алгоритмы, ранее опубликованные Бернардом Роем в 1959 году, а также Стивеном Уоршеллом в 1962 году для поиска транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликовано в 1956 г.) для преобразования детерминированного конечного автомата в регулярное выражение. Современная формулировка алгоритма в виде трёх вложенных циклов «for» была впервые описана Питером Ингерманом также в 1962 году.

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

---