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

ASA в 12:00, 4 июля 2022

2022-07-04T12:00:26Z

ASA: /* Количественная оценка локальности */

2022-04-28T14:06:43Z

Количественная оценка локальности

← Предыдущая версия		Версия от 14:06, 28 апреля 2022
Строка 121:		Строка 121:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/dijkstra/dijkstra.h здесь] (функция Kernel). Условия запуска описаны [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/dijkstra/dijkstra.h здесь] (функция Kernel). Условия запуска описаны [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].

	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

Bkmz12332: /* Общее описание алгоритма. */

2020-03-31T10:20:08Z

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

← Предыдущая версия		Версия от 10:20, 31 марта 2020
Строка 3:		Строка 3:

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

	'''Алгоритм Дейкстры'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа.		'''Алгоритм Дейкстры'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа.

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

2020-03-31T10:19:32Z

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

← Предыдущая версия		Версия от 10:19, 31 марта 2020
Строка 3:		Строка 3:

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

	'''Алгоритм Дейкстры'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа.		'''Алгоритм Дейкстры'''<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа.

Apaokin в 14:30, 15 июня 2018

2018-06-15T14:30:00Z

← Предыдущая версия		Версия от 14:30, 15 июня 2018
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}
	~~<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/5}} </indicator>~~
	Основные авторы описания: [[Участник:Daryin\|А.Н.Дарьин]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]])		Основные авторы описания: [[Участник:Daryin\|А.Н.Дарьин]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]])

Apaokin в 09:52, 15 июня 2018

2018-06-15T09:52:02Z

← Предыдущая версия		Версия от 09:52, 15 июня 2018
Строка 199:		Строка 199:
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).
	* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).
	* Gap {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}
	== Литература ==		== Литература ==

Apaokin в 09:04, 15 июня 2018

2018-06-15T09:04:02Z

← Предыдущая версия		Версия от 09:04, 15 июня 2018
Строка 199:		Строка 199:
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).
	* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).
			* Gap {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}
	== Литература ==		== Литература ==

Apaokin в 08:40, 15 июня 2018

2018-06-15T08:40:45Z

← Предыдущая версия		Версия от 08:40, 15 июня 2018
Строка 194:		Строка 194:

	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html dijkstra_shortest_paths]</code>, <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html dijkstra_shortest_paths_no_color_map]</code>), сложность <math>O(m + n \ln n)</math>.		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html dijkstra_shortest_paths]</code>, <code>[http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html dijkstra_shortest_paths_no_color_map]</code>), сложность <math>O(m + n \ln n)</math>.
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]:		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]: {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/14}}
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры;		** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры;
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<ref>Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.</ref> ~~{{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/14}}~~		** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<ref>Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.</ref>
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).
	* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).

Apaokin в 13:18, 14 июня 2018

2018-06-14T13:18:30Z

← Предыдущая версия		Версия от 13:18, 14 июня 2018
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}
			<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/5}} </indicator>
	Основные авторы описания: [[Участник:Daryin\|А.Н.Дарьин]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]])		Основные авторы описания: [[Участник:Daryin\|А.Н.Дарьин]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]])

Apaokin в 12:42, 14 июня 2018

2018-06-14T12:42:16Z

← Предыдущая версия		Версия от 12:42, 14 июня 2018
Строка 196:		Строка 196:
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]:		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]:
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры;		** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm eager_dijkstra_shortest_paths]</code> – непосредственная реализация алгоритма Дейкстры;
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<ref>Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.</ref>		** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#crauser-et-al-s-algorithm crauser_et_al_shortest_paths]</code> – реализация алгоритма Дейкстры в виде алгоритма из статьи Краузера и др.<ref>Crauser, A, K Mehlhorn, U Meyer, and P Sanders. “A Parallelization of Dijkstra's Shortest Path Algorithm,” Proceedings of Mathematical Foundations of Computer Science / Lecture Notes in Computer Science, 1450:722–31, Berlin, Heidelberg: Springer, 1998. doi:10.1007/BFb0055823.</ref> {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/14}}
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html single_source_dijkstra]</code>).
	* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.Dijkstra networkit.graph.Dijkstra]</code>).