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

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

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

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

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

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

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

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

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

Выкладываю реализацию алгоритма Дейкстры на С++ C++
Реализация алгоритма C++
C++ Реализация LCS алгоритма на с++
Задача с использованием алгоритма Дейкстры C++
C++ Реализация алгоритма
C++ Реализация алгоритма Дейкстры
Реализация алгоритма Прима C++
Определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры C++
C++ Не найден заголовочный файл в реализации алгоритма Дейкстры
Реализация циклического алгоритма C++
C++ Найти и исправить ошибки в реализации алгоритма Дейкстры
Реализация Алгоритма Грэхема на С++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
28.11.2013, 13:14     Параллельная реализация алгоритма Дейкстры #2
есть гипотеза, что Дейкстру (адекватно) распараллелить нельзя.
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
28.11.2013, 13:21  [ТС]     Параллельная реализация алгоритма Дейкстры #3
Если не трудно, киньте ссылку на материал.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
28.11.2013, 13:22     Параллельная реализация алгоритма Дейкстры #4
Цитата Сообщение от Perzh Посмотреть сообщение
Если не трудно, киньте ссылку на материал.
на какую тему материал?
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
28.11.2013, 14:21  [ТС]     Параллельная реализация алгоритма Дейкстры #5
Материал, на основании которого вы выдвинули такую гипотезу или где эта гипотеза описана =)
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
28.11.2013, 14:43     Параллельная реализация алгоритма Дейкстры #6
эта гипотеза описана тремя комментариями выше. основана она исключительно на том, что я знаю об алгоритме Дейкстры.
я не обдумывал особо этот вопрос. займитесь этим тщательно, может быть, получите интересный для всех результат.
Yandex
Объявления
28.11.2013, 14:43     Параллельная реализация алгоритма Дейкстры
Ответ Создать тему
Опции темы

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