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

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

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

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

Макроструктура алгоритма

Ключевая часть алгоритма состоит из трех циклов:
Для 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{ min({D_{ik}+D_{kj}}, D_{ij}) }[/math] и их значения становятся новыми значениями элементов смежной матрицы.

Схема реализации последовательного алгоритма

matrix - матрица смежности, numberOfVert - число вершин в графе

   //Пробегаемся по всем вершинам и ищем более короткий путь
   //через вершину k
   for(int k = 0; k < numberOfVert; k++) {
       for(int i = 0; i < numberOfVert; i++) {
          for(int j = 0; j < numberOfVert; j++) {
               //Новое значение ребра равно минимальному между старым
               //и суммой ребер i <-> k + k <-> j (если через k пройти быстрее)
               matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
           }
       }
   }

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

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

Информационный граф

Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла

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

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

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

Первый подход. В распоряжении имеется такое количество процессоров, что можно отдать каждому ровно по одному элементу [math]\displaystyle{ D_{ij} }[/math], чтобы он считал для этого элемента минимум.

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

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

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

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

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

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

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

Масштабируемость алгоритма и его реализации

Масштабируемость алгоритма

Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающие факторы:
1)Пропускная способность памяти при чтении данных графа.
2)Соперничество потоков при выполнении атомарных операций с памятью.
3)Синхронизация после каждого подшага алгоритма.

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

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

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