Алгоритм Флойда-Уоршелла: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
| Строка 2: | Строка 2: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Алгоритм Флойда-Уоршелла'''<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>. Алгоритм распознаёт наличие отрицательных циклов. | + | '''Алгоритм Флойда-Уоршелла'''<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> равными нулю, а недиагональные элементы, соответствующие не инцидентным вершинам (не имеющим общего ребра), положим равными бесконечности или числу, заведомо большему возможного расстояния между ребрами. | ||
| + | |||
| + | Ключевая часть алгоритма состоит из трех циклов:<br> | ||
| + | Для k от 1 до |V| выполнять <br> | ||
| + | Для i от 1 до |V| выполнять <br> | ||
| + | Для j от 1 до |V| выполнять <br> | ||
| + | Если <math>{D_{ik}+D_{kj} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. <br> | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Основной операцией алгоритма является релаксация элементов матрицы смежности: если <math>{D_{ik}+D_{kj} < D_{ij}}</math>, то производится присваивание <math>{D_{ij} := D_{ik}+D_{kj}}</math>. <br> | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| Строка 14: | Строка 28: | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| − | Входные данные: Матрица смежности | + | Входные данные: Матрица смежности D. Перед работой алгоритма матрица D заполняется длинами рёбер графа (или запредельно большим числом M, если ребра нет). <br> |
| − | Выходные данные: Матрица кратчайших расстояний | + | Выходные данные: Матрица кратчайших расстояний D. |
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 21:53, 22 октября 2017
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Флойда-Уоршелла[1][2][3] предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время [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 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Время выполнения этой программы, очевидно, имеет порядок [math]O(n^3)[/math], поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: Матрица смежности D. Перед работой алгоритма матрица D заполняется длинами рёбер графа (или запредельно большим числом M, если ребра нет).
Выходные данные: Матрица кратчайших расстояний D.
1.10 Свойства алгоритма
Алгоритм может распознавать наличие отрицательных циклов: такой цикл существует, если один из диагональных элементов матрицы расстояний становится меньше нуля.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- C++: Boost Graph Library (функция
floyd_warshall_shortest). - Python: NetworkX (функция
floyd_warshall). - Java: JGraphT (класс
FloydWarshallShortestPaths).
3 Литература
- ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
- ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
- ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
