Алгоритм Джонсона: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | == Свойства и структура алгоритма == |
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 6: | Строка 6: | ||
В случае разреженных графов алгоритм Джонсона эффективнее [[Алгоритм Флойда-Уоршелла|алгоритма Флойда-Уоршела]], имеющего сложность <math>O(n^3)</math>. Он применим к в случае произвольных (в том числе отрицательных) вещественных весов, в отличие от [[алгоритм Дейкстры]], имеющего ту же сложность. | В случае разреженных графов алгоритм Джонсона эффективнее [[Алгоритм Флойда-Уоршелла|алгоритма Флойда-Уоршела]], имеющего сложность <math>O(n^3)</math>. Он применим к в случае произвольных (в том числе отрицательных) вещественных весов, в отличие от [[алгоритм Дейкстры]], имеющего ту же сложность. | ||
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
Алгоритм Джонсона использует [[алгоритм Беллмана-Форда]] для предварительной обработки графа, заменяя веса рёбер на неотрицательные. Далее к получившемуся графу многократно применяется [[алгоритм Дейкстры]]. | Алгоритм Джонсона использует [[алгоритм Беллмана-Форда]] для предварительной обработки графа, заменяя веса рёбер на неотрицательные. Далее к получившемуся графу многократно применяется [[алгоритм Дейкстры]]. | ||
| Строка 15: | Строка 15: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 21: | Строка 21: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
Алгоритм Джонсона может быть эффективно распараллелен, так как применение алгоритма Дейкстры для каждой вершины производится независимо. Кроме того, вместо алгоритма Дейкстры можно использовать параллельный [[алгоритм Δ-шагания]]. | Алгоритм Джонсона может быть эффективно распараллелен, так как применение алгоритма Дейкстры для каждой вершины производится независимо. Кроме того, вместо алгоритма Дейкстры можно использовать параллельный [[алгоритм Δ-шагания]]. | ||
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | === | + | === Локальность данных и вычислений === |
| − | === Возможные способы и особенности реализации | + | ==== Локальность реализации алгоритма ==== |
| + | ===== Структура обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Масштабируемость алгоритма ==== | ||
| + | ==== Масштабируемость реализации алгоритма ==== | ||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| Строка 41: | Строка 47: | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
Версия 14:07, 29 июля 2015
Содержание
- 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] предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время [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.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 (функция
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.
