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

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

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

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

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

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

Алгоритм

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

Рассмотрим граф с номерами от 1 до  . Далее рассмотрим функцию, которая возвращает кратчайший путь от до с использованием вершин только из набора в качестве промежуточных точек по пути. Теперь, учитывая эту функцию, наша цель - найти кратчайший путь от каждого к каждому, используя любую вершину в . ${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle N}$${\ Displaystyle \ mathrm {shortPath} (я, j, k)}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ {1,2, \ ldots, к \}}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ {1,2, \ ldots, N \}}$

Для каждой из этих пар вершин может быть либо ${\ Displaystyle \ mathrm {shortPath} (я, 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 {ShortPath} (я, 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 ш (я, j)}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ mathrm {shortPath} (я, j, k)}$

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

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

${\ displaystyle \ mathrm {shortPath} (я, j, k) =}$

${\ displaystyle \ mathrm {min} {\ Big (} \ mathrm {shorttestPath} (i, j, k-1),}$

${\ displaystyle \ mathrm {shortPath} (я, к, k-1) + \ mathrm {shortPath} (k, j, k-1) {\ Big)}}$.

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

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

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

• Алгоритм Флойда – Уоршалла итеративно пересматривает длины путей между всеми парами вершин , включая where ;${\ displaystyle (я, j)}$${\ displaystyle i = j}$
• Изначально длина пути равна нулю;${\ Displaystyle (я, я)}$
• Путь может улучшить это, только если он имеет длину меньше нуля, то есть обозначает отрицательный цикл;${\ Displaystyle [я, к, \ ldots, я]}$
• Таким образом, после алгоритма, будет отрицательным, если существует путь отрицательной длины от back to .${\ Displaystyle (я, я)}$${\ displaystyle i}$${\ displaystyle i}$

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

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

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

Псевдокод

let dist be a ${\displaystyle |V|\times |V|}$ array of minimum distances initialized to ${\displaystyle \infty }$ (infinity)
let next be a ${\displaystyle |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)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[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]
                    next[i][j] ← next[i][k]

procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while u ≠ v
        u ← next[u][v]
        path.append(u)
    return path

Анализ

Позвольте быть , количество вершин. Для того, чтобы найти все из (для всех и ) от тех , требует операции. Так как мы начинаем с и вычислить последовательность матриц , , , , общее количество операций используются . Следовательно, сложность алгоритма составляет . ${\ displaystyle n}$${\ displaystyle | V |}$${\ Displaystyle п ^ {2}}$${\ Displaystyle \ mathrm {shortPath} (я, j, k)}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ mathrm {ShortPath} (я, j, k-1)}$${\ displaystyle 2n ^ {2}}$${\ Displaystyle \ mathrm {shortPath} (я, j, 0) = \ mathrm {edgeCost} (i, j)}$${\ displaystyle n}$${\ displaystyle \ mathrm {shortPath} (i, j, 1)}$${\ displaystyle \ mathrm {shortPath} (i, j, 2)}$${\ displaystyle \ ldots}$${\ displaystyle \ mathrm {shortPath} (i, j, n)}$${\ Displaystyle п \ cdot 2n ^ {2} = 2n ^ {3}}$${\ Displaystyle \ Theta (п ^ {3})}$

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

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

• Кратчайшие пути в ориентированных графах (алгоритм Флойда).
• Транзитивное замыкание ориентированных графов (алгоритм Уоршалла). В оригинальной формулировке алгоритма Уоршалла граф не взвешен и представлен булевой матрицей смежности . Затем операция сложения заменяется логическим соединением (И), а минимальная операция - логическим дизъюнкцией (ИЛИ).
• Нахождение регулярного выражения, обозначающего регулярный язык, принимаемый конечным автоматом ( алгоритм Клини , тесно связанное обобщение алгоритма Флойда – Уоршалла)
• Инверсия из вещественных матриц ( Gauss-Jordan алгоритм )
• Оптимальная маршрутизация. В этом приложении нужно найти путь с максимальным потоком между двумя вершинами. Это означает, что вместо взятия минимумов, как в псевдокоде выше, используются максимумы. Веса ребер представляют фиксированные ограничения потока. Веса путей представляют собой узкие места; поэтому операция сложения, указанная выше, заменяется минимальной операцией.
• Быстрое вычисление сетей Pathfinder .
• Самые широкие пути / пути с максимальной пропускной способностью
• Вычисление канонической формы матриц разностных границ (DBM)
• Вычисление сходства между графами
• Транзитивное замыкание в графах И / ИЛИ / порога.

Реализации

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

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

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

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

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

использованная литература

внешние ссылки

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