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

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

Версия 17:39, 11 июня 2015

Содержание

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

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

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

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

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 Существующие реализации алгоритма

Boost Graph Library (функция floyd_warshall_shortest).

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]

@@ Строка 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>. Алгоритм распознаёт наличие отрицательных циклов.
 === Математическое описание ===