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

Автор: Екатерина Шевченко

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

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

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

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

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

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

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

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

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

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

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

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

При этом вычисляются минимумы из двух чисел [math]min({D_{ik}+D_{kj}}, D_{ij})[/math] и их значения становятся новыми значениями элементов смежной матрицы.

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

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]);
           }
       }
   }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова. Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи.

Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.

Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.

Как видно из представленных графиков параллельный алгоритм сильно масштабируем.

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

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