Алгоритм Джонсона: различия между версиями

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

Версия 23:03, 30 июня 2015

Содержание

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

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

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

Алгоритм Джонсона^[1] предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время [math]O(mn + n^2 \ln n)[/math].

В случае разреженных графов алгоритм Джонсона эффективнее алгоритма Флойда-Уоршела, имеющего сложность [math]O(n^3)[/math]. Он применим к в случае произвольных (в том числе отрицательных) вещественных весов, в отличие от алгоритм Дейкстры, имеющего ту же сложность.

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

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

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

Основными вычислительными блоками алгоритма Джонсона являются алгоритм Беллмана-Форда и алгоритм Дейкстры.

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

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

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

На этапе предварительной обработки выполняется алгоритм Беллмана-Форда сложностью [math]O(mn)[/math]. Далее для каждой вершины графа выполняется алгоритм Дейкстры сложностью [math]O(m + n \ln n)[/math]. Итоговая сложность алгоритма Джонсона [math]O(mn + n^2 \ln n)[/math].

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

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

Алгоритм Джонсона может быть эффективно распараллелен, так как применение алгоритма Дейкстры для каждой вершины производится независимо. Кроме того, вместо алгоритма Дейкстры можно использовать параллельный алгоритм Δ-шагания.

1.9 Описание входных и выходных данных

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

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

C++: Boost Graph Library (функция johnson_all_pairs_shortest_paths).

3 Литература

↑ Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.

[1] Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.

[1]

@@ Строка 35: / Строка 35: @@
 === Выводы для классов архитектур ===
 === Существующие реализации алгоритма ===
+* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html johnson_all_pairs_shortest_paths]</code>).
 == Литература ==
 <references />