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

Свойства и структура алгоритма

Общее описание алгоритма

Алгоритм Флойда-Уоршелла предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время [math]\displaystyle{ O(n^3) }[/math]. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с алгоритмом Дейкстры, который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

Математическое описание алгоритма

Имеем граф [math]\displaystyle{ G=(V,E) }[/math], в котором каждая вершина пронумерована от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ |V| }[/math]. Сформируем матрицу смежности [math]\displaystyle{ D }[/math]. Эта матрица имеет размер [math]\displaystyle{ |V|*|V| }[/math] и каждому ее элементу [math]\displaystyle{ D_{ij} }[/math] присвоен вес ребра, соединяющего вершину [math]\displaystyle{ i }[/math] с вершиной [math]\displaystyle{ j }[/math]. Заметим, что в силу ориентированности графа [math]\displaystyle{ G }[/math] матрица [math]\displaystyle{ D }[/math] может быть несимметрична.

По мере выполнения алгоритма данная матрица будет перезаписываться: в каждую из ее ячеек внесется значение, определяющее оптимальную длину пути из вершины [math]\displaystyle{ i }[/math] в вершину [math]\displaystyle{ j }[/math].

Полагаем диагональные элементы [math]\displaystyle{ D_{ii} }[/math] равными нулю, а недиагональные элементы, соответствующие не инцидентным вершинам (не имеющим общего ребра), положим равными бесконечности или числу, заведомо большему возможного расстояния между ребрами.

Ключевая часть алгоритма состоит из трех циклов:
Для k от 1 до |V| выполнять
Для i от 1 до |V| выполнять
Для j от 1 до |V| выполнять
Если [math]\displaystyle{ {D_{ik}+D_{kj} \lt D_{ij}} }[/math], то [math]\displaystyle{ {D_{ij} := D_{ik}+D_{kj}} }[/math].

Вычислительное ядро алгоритма

Основной операцией алгоритма является релаксация элементов матрицы смежности: если [math]\displaystyle{ {D_{ik}+D_{kj} \lt D_{ij}} }[/math], то производится присваивание [math]\displaystyle{ {D_{ij} := D_{ik}+D_{kj}} }[/math].

Последовательная сложность алгоритма

Время выполнения этой программы, очевидно, имеет порядок [math]\displaystyle{ O(n^3) }[/math], поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

Ресурс параллелизма алгоритма

В последовательном алгоритме единственная операция это нахождение минимума, ее нет смысла распараллеливать. Вся сложность алгоритма $(О^3)$ заключается в полном переборе «матрицы смежности». Идея параллельных схем алгоритма Флойда-Уоршелла состоит в том, чтобы модифицировать матрицу смежности одновременно несколькими процессорами. Можно выделить два основных подхода.

Первый подход. В распоряжении имеется такое количество процессоров, что можно отдать каждому ровно по одному элементу $D_ij$, чтобы он считал для этого элемента минимум.

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

Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы $D$. Всего в подзадачах $n^2/p$ таких элементов, число итераций алгоритма равно $n$, таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид ($p$ – число процессоров): &Sp = n^3/(n^3/p) = p$, $Ep = n^3/(p(n^3⁄p)) = 1$.

Входные и выходные данные алгоритма

Входные данные: Матрица смежности D. Перед работой алгоритма матрица D заполняется длинами рёбер графа (или запредельно большим числом M, если ребра нет).
Выходные данные: Матрица кратчайших расстояний D.

Свойства алгоритма

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

Программная реализация алгоритма

Существующие реализации алгоритма

• C++: Boost Graph Library (функция floyd_warshall_shortest).
• Python: NetworkX (функция floyd_warshall).
• Java: JGraphT (класс FloydWarshallShortestPaths).