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

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

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

Алгоритм Флойда-Уоршелла предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время [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], поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

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

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

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

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

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

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

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