Введение
Алгоритм поиска кратчайших путей между всеми парами вершин в графах, допускающий отрицательные веса некоторых рёбер.
В информатике алгоритм Флойда — Уоршалла (также известный как алгоритм Флойда, алгоритм Роя — Уоршалла, алгоритм Роя — Флойда или алгоритм WFI) — это алгоритм для нахождения кратчайших путей во взвешенном ориентированном графе с положительными или отрицательными весами рёбер (но без отрицательных циклов). Однократное выполнение алгоритма позволяет найти длины (сумму весов) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, их можно восстановить с помощью простых модификаций алгоритма. Различные варианты алгоритма также могут использоваться для нахождения транзитивного замыкания отношения или (в связи с системой голосования Шульце) самых широких путей между всеми парами вершин во взвешенном графе.
История и названия
Алгоритм Флойда — Уоршалла является примером динамического программирования и был опубликован в его современной, общепринятой форме Робертом Флойдом в 1962 году. Однако, по сути, он идентичен алгоритмам, ранее опубликованным Бернардом Роем в 1959 году и Стивеном Уоршаллом в 1962 году для вычисления транзитивного замыкания графа, и тесно связан с алгоритмом Клини (опубликованным в 1956 году) для преобразования детерминированного конечного автомата в регулярное выражение. Современная формулировка алгоритма в виде трех вложенных циклов впервые была описана Питером Ингерманом, также в 1962 году.
Алгоритм
Алгоритм Флойда — Уоршалла сравнивает множество возможных путей в графе между каждой парой вершин. Он гарантированно находит все кратчайшие пути и способен делать это с помощью сравнений в графе с вершинами. Во время выполнения алгоритма, если присутствует отрицательный цикл, могут возникать экспоненциально большие числа, достигающие , где — наибольшее абсолютное значение веса отрицательного ребра в графе. Чтобы избежать проблем переполнения или потери точности, следует проверять наличие отрицательных чисел на диагонали матрицы расстояний во внутренней петле алгоритма. Очевидно, что в ненаправленном графе отрицательное ребро создает отрицательный цикл (то есть замкнутый путь), включающий его инцидентные вершины. Например, если рассматривать все ребра вышеуказанного графа как ненаправленные, то последовательность вершин 4 – 2 – 4 является циклом с суммарным весом −2.
Реконструкция трассы
Алгоритм Флойда — Уоршелла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод для восстановления фактического пути между любыми двумя конечными вершинами. Хотя может возникнуть соблазн хранить сам путь от каждой вершины к каждой другой, это не требуется и, более того, очень затратно по памяти. Вместо этого можно использовать дерево кратчайших путей, которое можно вычислить для каждого узла за время, используя объем памяти, и которое позволяет эффективно восстановить путь между любыми двумя связанными вершинами.
Сравнение с другими алгоритмами кратчайшего пути
Для графов с неотрицательными весами ребер алгоритм Дейкстры может быть использован для нахождения всех кратчайших путей от одной вершины за время выполнения. Таким образом, запуск алгоритма Дейкстры, начиная с каждой вершины, занимает время. Поскольку , это дает наихудшее время выполнения, равное повторному применению алгоритма Дейкстры. Хотя это соответствует асимптотическому наихудшему времени выполнения алгоритма Флойда-Уоршалла, константы, участвующие в вычислениях, имеют большое значение. Когда граф плотный (т.е. ), алгоритм Флойда-Уоршалла, как правило, работает лучше на практике. Когда граф разреженный (т.е. значительно меньше ), алгоритм Дейкстры обычно оказывается эффективнее. Для разреженных графов с отрицательными ребрами, но без отрицательных циклов, можно использовать алгоритм Джонсона, с тем же асимптотическим временем выполнения, что и при повторном применении алгоритма Дейкстры. Существуют также известные алгоритмы, использующие быстрое умножение матриц для ускорения вычисления кратчайших путей между всеми парами вершин в плотных графах, но они обычно накладывают дополнительные ограничения на веса ребер (например, требуют, чтобы они были небольшими целыми числами). Кроме того, из-за высоких постоянных факторов в их времени работы, они обеспечат ускорение по сравнению с алгоритмом Флойда-Уоршалла только для очень больших графов.