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