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

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

Алгоритм Флойда — Уоршелла
Floyd-Warshall-Algorithm-Problem.png
Назван в честь Роберт Флойд и Уоршелл, Стивен
Автор Bernard Roy[d]
Предназначение поиск в графе кратчайших путей между любыми парами вершин
Структура данных граф
Худшее время
Лучшее время
Среднее время
Затраты памяти
Логотип Викисклада Медиафайлы на Викискладе

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

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

АлгоритмПравить

Рассмотрим граф   с вершинами  , пронумерованными от 1 до  . Алгоритм Флойда–Уоршелла сравнивает все возможные пути через граф между каждой парой вершин. Он может сделать это за   сравнений в графе, даже если в графе может быть до   ребер, и каждая комбинация ребер проверяется. Это достигается путем постепенного улучшения оценки кратчайшего пути между двумя вершинами, пока оценка не станет оптимальной.

Далее рассмотрим функцию  , которая возвращает кратчайший возможный путь от   до   с использованием вершин только из множества   в качестве промежуточных точек на этом пути . Теперь, учитывая эту функцию, наша цель - найти кратчайший путь от каждого   до каждого  , используя любую вершину в  .

Для каждой из этих пар вершин   может быть либо

(1) путь, который не проходит через   (использует только вершины из набора  .)

или

(2) путь, который проходит через   (от   до   и затем от   до  , в обоих случаях используются только промежуточные вершины в  ))

Мы знаем, что лучший путь от   до  , это путь который использует только вершины c   по  , определяется как  , и ясно, что если бы существовал лучший путь от   до   до  , тогда длина этого пути была бы цепочкой самых коротких путь от   до   (только с использованием промежуточных вершин в  ) и кратчайший путь от   до   (только с использованием промежуточных вершин в  ).

Если   - вес ребра между вершинами   и  , мы можем определить   в терминах следующей рекурсивной формулой:

базовый случай

 

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

 
 
 .

Эта формула составляет основу алгоритма Флойда–Уоршелла. Алгоритм работает, сначала вычисляя   для всех пар   для  , а затем  , и так далее. Этот процесс продолжается до тех пор, пока   не будет найден кратчайший путь для всех пар   с использованием любых промежуточных вершин. Псевдокод для этой базовой версии следующий:

let dist be a |V| × |V| массив минимальных расстояний, инициализированный как ∞ (бесконечность)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // Вес ребра (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 j
1 2 3 4
i 1 0 −2
2 4 0 3
3 0 2
4 −1 0
k = 1 j
1 2 3 4
i 1 0 −2
2 4 0 2
3 0 2
4 −1 0
k = 2 j
1 2 3 4
i 1 0 −2
2 4 0 2
3 0 2
4 3 −1 1 0
k = 3 j
1 2 3 4
i 1 0 −2 0
2 4 0 2 4
3 0 2
4 3 −1 1 0
k = 4 j
1 2 3 4
i 1 0 −1 −2 0
2 4 0 2 4
3 5 1 0 2
4 3 −1 1 0

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

Отрицательный цикл - это цикл, сумма ребер которого равна отрицательному значению. Не существует кратчайшего пути между любой парой вершин  ,  , которые являются частью отрицательного цикла, потому что длина пути от   до   может быть сколь угодно малой (отрицательный). Для численно значимого вывода алгоритм Флойда–Уоршелла предполагает отсутствие отрицательных циклов. Тем не менее, если есть отрицательные циклы, алгоритм Флойда–Уоршелла может быть использован для их обнаружения. Очевидно алгоритм заключается в следующем:

  • Алгоритм Флойда–Уоршелла итеративно просматривает длину пути

между всеми парами вершин  , включая те где  ;

  • Изначально длина пути   равна нулю;
  • Путь   может улучшиться только в том случае, если его длина

меньше нуля, т.е. обозначает отрицательный цикл;

  • Таким образом, после алгоритма,   будет отрицательным, если

существует путь отрицательной длины от   до  .

Следовательно, чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда–Уоршелла, можно проверить диагональ матрицы кратчайших путей, и наличие отрицательного числа указывает на то, что граф содержит по крайней мере один отрицательный цикл. Во время выполнения алгоритма, если есть отрицательный цикл, могут появиться экспоненциально большие числа, вплоть до  , где   - наибольшее абсолютное значение отрицательного ребра в графе. Чтобы избежать проблем переполнения/потери значимости, следует проверять наличие отрицательных чисел на диагонали матрицы кратчайших путей внутри внутреннего цикла for алгоритма. Очевидно, что в неориентированном графе отрицательное ребро создает отрицательный цикл (то есть замкнутый обход), включающий его инцидентные вершины. Рассматривая все ребра приведенного выше примера графа как неориентированные, например последовательность вершин 4 - 2 - 4 представляет собой цикл с весовой суммой - 2.

Реконструкция путейПравить

Алгоритм Флойда–Уоршелла обычно предоставляет только длины путей между всеми парами вершин. С помощью простых модификаций можно создать метод восстановления фактического пути между любыми двумя вершинами конечной точки. Хотя кто-то может быть склонен хранить 3 фактический путь от каждой вершины к каждой другой вершине, это не обязательно, и на самом деле это очень дорого с точки зрения памяти. Вместо этого дерево кратчайших путей может быть вычислено для каждого узла за   время, используя память   для хранения каждого дерева, что позволяет нам эффективно реконструировать путь из любых двух связанных вершин.

Псевдокод [1]Править

let dist be a   массив минимальных расстояний, инициализированный как   (бесконечность)
let next be a   массив индексов вершин, инициализированный null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // Вес ребра (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // стандартная реализация алгоритма Флойда–Уоршелла
        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]
                    next[i][j] ← next[i][k]
procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while uv
        u ← next[u][v]
        path.append(u)
    return path

Анализ сложности АлгоритмаПравить

Пусть   будет   количеством вершин. Чтобы найти все   из   (для всех   и  ) из s  требуется   операций. Поскольку мы начинаем с  и вычисляем последовательность   матриц  ,  ,  ,  , общее количество используемых операций равно  . Следовательно, сложность алгоритма равна  .

Приложения и обобщенияПравить

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

РеализацииПравить

Сравнение с другими алгоритмамиПравить

Алгоритм Флойда–Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет   при применении двоичной кучи, что лучше, чем   алгоритма Флойда–Уоршелла тогда, когда   существенно меньше   (условие разреженности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

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

ПримечанияПравить

  1. Free Algorithms Book
  2. Zwick, Uri (May 2002), All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM Т. 49 (3): 289–317, DOI 10.1145/567112.567114 .
  3. Chan, Timothy M. (January 2010), More algorithms for all-pairs shortest paths in weighted graphs, SIAM Journal on Computing Т. 39 (5): 2075–2089, DOI 10.1137/08071990x .

ЛитератураПравить