Алговики - Вклад [ru]

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

2017-12-01T08:11:29Z

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

Автор: Екатерина Шевченко
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

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

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

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

[[file: Pic1.jpg|thumb|center|700px|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

[[file: Pic3.jpg|thumb|center|700px|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-12-01T08:11:06Z

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

Автор: Екатерина Шевченко
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

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

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

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

[[file: Pic1.jpg|thumb|center|700px|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

[[file: Pic3.jpg|thumb|center|700px|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T22:24:26Z

EkaterinaShevchenko: /* Свойства и структура алгоритма */

Автор: Екатерина Шевченко
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

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

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

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

[[file: Pic1.jpg|thumb|center|700px|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

[[file: Pic3.jpg|thumb|center|700px|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T22:23:02Z

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

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

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

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

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

[[file: Pic1.jpg|thumb|center|700px|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

[[file: Pic3.jpg|thumb|center|700px|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T20:54:52Z

EkaterinaShevchenko: /* Масштабируемость алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

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

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

==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T20:13:00Z

EkaterinaShevchenko: /* Информационный граф */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.

=== Информационный граф ===
[[file:Graphforfloyd.png|thumb|center|300px|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

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

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

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T19:03:50Z

EkaterinaShevchenko: /* Свойства и структура алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

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

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

При этом вычисляются минимумы из двух чисел <math>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>O(n^3)</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>.

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T18:56:33Z

EkaterinaShevchenko: /* Свойства и структура алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===

'''Алгоритм Флойда-Уоршелла'''<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref><ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(n^3)</math>. Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с [[Алгоритм Дейкстры|алгоритмом Дейкстры]], который не работает с отрицательными весами ребер. Также алгоритм распознаёт наличие отрицательных циклов.

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

Имеем граф <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} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. 
=== Вычислительное ядро алгоритма ===

Основной операцией алгоритма является релаксация элементов матрицы смежности: если <math>{D_{ik}+D_{kj} < D_{ij}}</math>, то производится присваивание <math>{D_{ij} := D_{ik}+D_{kj}}</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>O(n^3)</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>.

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html floyd_warshall_shortest]</code>).
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html floyd_warshall]</code>).
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html FloydWarshallShortestPaths]</code>).

== Литература ==

<references />

[[Категория:Начатые статьи]]

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

2017-11-30T18:32:24Z

EkaterinaShevchenko: /* Свойства и структура алгоритма */

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

2017-11-30T18:10:52Z

EkaterinaShevchenko: /* Ресурс параллелизма алгоритма */

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

2017-11-30T18:08:00Z

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

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

2017-11-30T18:07:42Z

EkaterinaShevchenko: /* Ресурс параллелизма алгоритма */

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

2017-10-22T18:53:42Z

EkaterinaShevchenko: /* Свойства и структура алгоритма */