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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25
28.11.2013, 12:35     Параллельная реализация алгоритма Дейкстры #1
Здравствуйте. Вообщем, надо сделать алгоритм Дейкстры на MPI, но выполнятся он будет не на кластере, а на одном компе.
(далее узел - вычислительный узел)

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

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

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

C++ Реализация алгоритма Мандельброта
Выкладываю реализацию алгоритма Дейкстры на С++ C++
Реализация алгоритма C++
Реализация алгоритма RLE 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     Параллельная реализация алгоритма Дейкстры
Ответ Создать тему
Опции темы

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