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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация волнового алгоритма - C++
Делаю игру Пакман В Игре имеются следующие классы Map.h #ifndef MAP_H #define MAP_H #include <SFML\Graphics.hpp>

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

Реализация алгоритма FOREL - C++
Не буду слишком наглым и не буду просить готовое решение, но вопросы будут на каждом шагу! для начала, не сильно раньше заморачивался,...

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

Реализация алгоритма Йена на С++ - C++
помогите пожалуста реализовать алгоритм Йена есть алгоритм Дейкстры нужно его доделать до Йена#include<iostream> #include<string.h> ...

Шифр ГОСТ, реализация алгоритма - C++
Здравствуйте, решил реализовать ГОСТ, но он не работает, не могу понять в чем ошибка. Может что-то делаю не так в плане алгоритма самого...

Реализация алгоритма сжатия JPEG - C++
помогите пожалуйста! после завтра диплом уже защищать, а я ни на шаг не могу сдвинуться с этой прогрммой(( нужно написать на С++ алгоритм...


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

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

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