Алгоритм Флойда-Уоршелла: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Строка 28: Строка 28:
=== Информационный граф ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Ресурс параллелизма алгоритма ===
В последовательном алгоритме единственная операция это нахождение минимума, ее нет смысла распараллеливать. Вся сложность алгоритма заключается в полном переборе «матрицы смежности». Идея параллельных схем алгоритма Флойда-Уоршелла состоит в том, чтобы модифицировать матрицу смежности одновременно несколькими процессорами. Можно выделить два основных подхода.
В последовательном алгоритме единственная операция - это нахождение минимума, ее нет смысла распараллеливать. Вся сложность алгоритма заключается в полном переборе «матрицы смежности». Идея параллельных схем алгоритма Флойда-Уоршелла состоит в том, чтобы модифицировать матрицу смежности одновременно несколькими процессорами. Можно выделить два основных подхода.


Первый подход. В распоряжении имеется такое количество процессоров, что можно отдать каждому ровно по одному элементу <math>{D_{ij}}<math>, чтобы он считал для этого элемента минимум.
Первый подход. В распоряжении имеется такое количество процессоров, что можно отдать каждому ровно по одному элементу <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>.
Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы <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>.


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

Версия от 18:32, 30 ноября 2017

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

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

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

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

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

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

Первый подход. В распоряжении имеется такое количество процессоров, что можно отдать каждому ровно по одному элементу [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. ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  2. ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  3. ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Алгоритм_Флойда-Уоршелла&oldid=24688