Алгоритм Джонсона - История изменений

ASA в 07:31, 5 июля 2022

2022-07-05T07:31:31Z

← Предыдущая версия		Версия от 07:31, 5 июля 2022
Строка 32:		Строка 32:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* 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>).

	== Литература ==		== Литература ==

ASA в 13:42, 14 марта 2018

2018-03-14T13:42:24Z

← Предыдущая версия		Версия от 13:42, 14 марта 2018
Строка 51:		Строка 51:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Johnson's algorithm]]

ASA в 14:11, 6 марта 2018

2018-03-06T14:11:36Z

← Предыдущая версия		Версия от 14:11, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:07, 29 июля 2015

2015-07-29T11:07:38Z

← Предыдущая версия		Версия от 11:07, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

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

	=== Математическое описание ===		=== Математическое описание алгоритма ===

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

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 21:		Строка 21:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

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

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 41:		Строка 47:

	<references />		<references />

			[[Категория:Начатые статьи]]

Daryin: /* Существующие реализации алгоритма */

2015-06-30T20:03:55Z

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

← Предыдущая версия		Версия от 20:03, 30 июня 2015
Строка 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 />		<references />

Daryin: Опечатки

2015-06-30T19:53:14Z

Опечатки

← Предыдущая версия		Версия от 19:53, 30 июня 2015
Строка 8:		Строка 8:
	=== Математическое описание ===		=== Математическое описание ===

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

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

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

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

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

2015-06-30T19:51:41Z

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

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Джонсона'''<ref>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.</ref> предназначен для решения [[Поиск кратчайшего пути для всех пар вершин (APSP)|задачи поиска всех кратчайших путей на графе]]. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время <math>O(mn + n^2 \ln n)</math>.

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

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

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

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

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

=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===

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

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===

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

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />