Алгоритм Беллмана-Форда - История изменений

ASA в 13:32, 4 июля 2022

2022-07-04T13:32:15Z

ASA: /* Макроструктура алгоритма */

2022-07-04T13:00:24Z

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

← Предыдущая версия		Версия от 13:00, 4 июля 2022
Строка 35:		Строка 35:
	2. Релаксация множества рёбер <math>E</math>		2. Релаксация множества рёбер <math>E</math>

	а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t^' (z)=t(v)+ w(e)</math>.		а) Для каждого ребра <math>e=(v,z) \in E</math> вычисляется новое предполагаемое расстояние <math>t' (z)=t(v)+ w(e)</math>.

	б) Если <math>t^' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math> ).		б) Если <math>t' (z)< t(z)</math>, то происходит присваивание <math>t(z) := t' (z)</math> (релаксация ребра <math>e</math>).

	3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.		3. Алгоритм производит релаксацию всех рёбер графа до тех пор, пока на очередной итерации происходит релаксация хотя бы одного ребра.

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

2018-06-15T14:32:18Z

← Предыдущая версия		Версия от 14:32, 15 июня 2018
Строка 1:		Строка 1:
	~~<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/6}} </indicator>~~
	{{algorithm		{{algorithm
	\| name = Алгоритм Беллмана-Форда		\| name = Алгоритм Беллмана-Форда

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

2018-06-15T08:59:04Z

← Предыдущая версия		Версия от 08:59, 15 июня 2018
Строка 206:		Строка 206:
	* Nvidia nvGraph {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/19}}		* Nvidia nvGraph {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/19}}
	* Graph500 MPI {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/24}}		* Graph500 MPI {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/24}}
	* Ligra {{http://top53.parallel.ru/algo_results/implementation/41}}		* Ligra {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/41}}
	== Литература ==		== Литература ==

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

2018-06-15T08:58:22Z

← Предыдущая версия		Версия от 08:58, 15 июня 2018
Строка 203:		Строка 203:
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford.html bellman_ford]</code>).
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html BellmanFordShortestPath]</code>).		* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BellmanFordShortestPath.html BellmanFordShortestPath]</code>).
			* OpenMP Stinger {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/10}}
			* Nvidia nvGraph {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/19}}
			* Graph500 MPI {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/24}}
			* Ligra {{http://top53.parallel.ru/algo_results/implementation/41}}
	== Литература ==		== Литература ==

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

2018-06-15T08:31:08Z

← Предыдущая версия		Версия от 08:31, 15 июня 2018
Строка 1:		Строка 1:
			<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/6}} </indicator>
	{{algorithm		{{algorithm
	\| name = Алгоритм Беллмана-Форда		\| name = Алгоритм Беллмана-Форда
Строка 7:		Строка 8:
	\| output_data = <math>O(\|V\|^2)</math>		\| output_data = <math>O(\|V\|^2)</math>
	}}		}}
	~~<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/6}} </indicator>~~

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

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

2018-06-14T13:14:59Z

← Предыдущая версия		Версия от 13:14, 14 июня 2018
Строка 7:		Строка 7:
	\| output_data = <math>O(\|V\|^2)</math>		\| output_data = <math>O(\|V\|^2)</math>
	}}		}}
	<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/5}} </indicator>		<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/6}} </indicator>
	~~http://top53.parallel.ru/algo_results/algorithm/6~~
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

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

2018-06-14T13:14:26Z

← Предыдущая версия		Версия от 13:14, 14 июня 2018
Строка 7:		Строка 7:
	\| output_data = <math>O(\|V\|^2)</math>		\| output_data = <math>O(\|V\|^2)</math>
	}}		}}
			<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/5}} </indicator>
			http://top53.parallel.ru/algo_results/algorithm/6
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

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

2017-11-26T17:13:52Z

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

← Предыдущая версия		Версия от 17:13, 26 ноября 2017
Строка 189:		Строка 189:
	[[file:Bellman-Ford Inf Data.png\|thumb\|center\|700px\|Рисунок 13. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Беллмана-Форда]]		[[file:Bellman-Ford Inf Data.png\|thumb\|center\|700px\|Рисунок 13. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Беллмана-Форда]]

	На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на ~~кпервом~~ этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.		На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.

	[[file:Bellman-Ford Inf Pckts.png\|thumb\|center\|700px\|Рисунок 14. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Беллмана-Форда]]		[[file:Bellman-Ford Inf Pckts.png\|thumb\|center\|700px\|Рисунок 14. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Беллмана-Форда]]

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

2017-11-26T14:52:54Z

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

← Предыдущая версия		Версия от 14:52, 26 ноября 2017
Строка 179:		Строка 179:
	На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 140 млн/сек. Это очень высокий показатель, показывающий потенциальную причину неэффективности.		На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 140 млн/сек. Это очень высокий показатель, показывающий потенциальную причину неэффективности.

	[[file:Bellman-Ford L2.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Беллмана-Форда]]		[[file:Bellman-Ford L2.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L2 в секунду при работе алгоритма Беллмана-Форда]]

	На графике кэш-промахов второго уровня видно, что число промахов ~~достаточно~~ тоже крайне высокое и находится на уровне 140 млн/сек, что указывает на крайне неэффективную работу с памятью.		На графике кэш-промахов второго уровня видно, что число таких промахов тоже крайне высокое и находится на уровне 140 млн/сек, что указывает на крайне неэффективную работу с памятью.

	[[file:Bellman-Ford-L3.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма Беллмана-Форда]]		[[file:Bellman-Ford-L3.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма Беллмана-Форда]]