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

[непроверенная версия]

Версия 10:10, 31 мая 2017

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

[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.

[1]

[2]

[3]

@@ Строка 9: / Строка 9: @@
 === Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
-Время выполнения этой программы, очевидно, имеет порядок <math>O(n^3)</math, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.
+Время выполнения этой программы, очевидно, имеет порядок <math>O(n^3)</math>, поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов.
 === Информационный граф ===