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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 27: Строка 27:
 
* 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>).
 
* 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>).
 
* 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 />
 
<references />

Версия 22:44, 11 июня 2015

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

3 Литература

  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.