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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Дано натуральное число. Определить номер цифры «8» http://www.cyberforum.ru/cpp-beginners/thread1021724.html
Дано натуральное число. Определить номер цифры «8» в нем, считая от конца числа. Если такой цифры нет, ответом должно быть число 0, если таких цифр в числе несколько — должен быть определен номер...
C++ Подскажите как сделать ввод с клавиатуры пользователем #include <cstdlib> #include <iostream> using namespace std; class String { private: char* str; int n; http://www.cyberforum.ru/cpp-beginners/thread1021708.html
C++ Я новичок , не могу дописать программу
Найти ту непрерывную последовательность положительных чисел, сумма элементов в которой максимальная. Подсказка:В цикле идешь по массиву и до первого положительного. Нашел - идешь дальше считаешь...
Сортировка по алфавиту C++
Ребят, нужна помощь. Суть задания: сформировать список книг и отсортировать его по ФИО автора. Сам список я создал, но помогите написать сортировку этого списка по алфавиту по ФИО автора.Заранее...
C++ Не понимаю как доделать программу http://www.cyberforum.ru/cpp-beginners/thread1021695.html
Требования: нужно,организовать массив из тех чисел, которые входят в последовательность более одного раза. Вот я создал 2 массива, заполнил их числами, как теперь сделать так,чтобы...
C++ Объект общего вида (Object) в консольном приложении Всем привет. Не смог понять одной вещи: есть ли возможность создать функцию с аргументом типа Object(Любой объект, чтоб, что я туда не передам - всё бы съелось), как в VB, C#, Java или Obcect... подробнее

Показать сообщение отдельно
Perzh
0 / 0 / 0
Регистрация: 20.01.2013
Сообщений: 25

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

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

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

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

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

Собственно вопрос: если не трудно, поделитесь идеями как это дело можно эффективно распараллелить? И имеет ли вообще смысл распараллеливать поиск из А в В (если не требуется найти путь до всех вершин графа сразу)? Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru