Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
#1

Параллельная реализация алгоритма Дейкстры - C++

28.11.2013, 12:35. Просмотров 1388. Ответов 5
Метки нет (Все метки)

Здравствуйте. Вообщем, надо сделать алгоритм Дейкстры на MPI, но выполнятся он будет не на кластере, а на одном компе.
(далее узел - вычислительный узел)

Первое, что мне пришло в голову, это просто параллельно прочесывать граф в поиске искомой вершины несколькими узлами. Все узлы пишут в общую память. Правда это больше похоже на волновой алгоритм. И к тому же у меня сложилось мнение, что организовать общую память на MPI - настоящий гемор. Во всяком случае это будет не слишком правильно идеологически.

Второе о чем я подумал, это параллельно найти кратчайшие пути до всех соседей искомой вершины. Затем каждый узел вычислит самое выгодное ребро в своём диапазоне соседей и отправит его главному узлу, который уже вынесет окончательные вердикт.

Собственно вопрос: если не трудно, поделитесь идеями как это дело можно эффективно распараллелить? И имеет ли вообще смысл распараллеливать поиск из А в В (если не требуется найти путь до всех вершин графа сразу)? Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2013, 12:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Параллельная реализация алгоритма Дейкстры (C++):

Реализация алгоритма Дейкстры - C++
Кто может подсказать (или указать где найти) код алгоритма Дейкстры на С++?

Задача с использованием алгоритма Дейкстры - C++
Ребят,кто-нибудь помогите решить задачку, используя алгоритм Дейкстры.Он есть готовый,осталось с помощью него только решить. Задача об...

Выкладываю реализацию алгоритма Дейкстры на С++ - C++
Дпанная программа выполняет поиск по заданной матрице весов. Далее указываем начальную точку в графе и программа расчитывает все кратчайшие...

Не найден заголовочный файл в реализации алгоритма Дейкстры - C++
запускаю программу и выдает ошибку "fatal error C1083: Не удается открыть файл включение: stdafx.h: No such file or directory" код...

Найти и исправить ошибки в реализации алгоритма Дейкстры - C++
Алгоритм Дейкстры (построение путей с минимальными цепями) #include<iostream.h> #include<string.h> #include<stdio.h> ...

Определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры - C++
Реализация АТД « Взвешенный орграф». Граф представлен в виде списков смежности. Определение радиуса и соответствующего радиусу пути...

5
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
28.11.2013, 13:14 #2
есть гипотеза, что Дейкстру (адекватно) распараллелить нельзя.
1
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
28.11.2013, 13:21  [ТС] #3
Если не трудно, киньте ссылку на материал.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
28.11.2013, 13:22 #4
Цитата Сообщение от Perzh Посмотреть сообщение
Если не трудно, киньте ссылку на материал.
на какую тему материал?
0
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
28.11.2013, 14:21  [ТС] #5
Материал, на основании которого вы выдвинули такую гипотезу или где эта гипотеза описана =)
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
28.11.2013, 14:43 #6
эта гипотеза описана тремя комментариями выше. основана она исключительно на том, что я знаю об алгоритме Дейкстры.
я не обдумывал особо этот вопрос. займитесь этим тщательно, может быть, получите интересный для всех результат.
0
28.11.2013, 14:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2013, 14:43
Привет! Вот еще темы с ответами:

Реализация алгоритма - C++
Смотрите, есть функция для рисования сегмента круга: pieslice(int x, int y, int start, int end, int radius) - int start и int ende угол...

Реализация алгоритма - C++
помогите пожалуйсто написать программу: 1. Реализовать алгоритм Insertion-Sort (сортировка вставками) и Merge-Sort (сортировка слиянием)...

Реализация алгоритма Мандельброта - C++
Знаю, этим уже давно никого не удивить, но я еще раз решил почтить память Бенуа Мандельброта простой коонсльной программой с реализацией...

Реализация алгоритма DBSCAN - C++
Всем добрый день/ночь! Есть такой алгоритм кластеризации DBSCAN Я его реализовал на c++/qt Хотелось бы узнать у...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru