2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Параллельная реализация алгоритма Дейкстры [MPI]
Сообщение28.11.2013, 16:06 
Здравствуйте. Вообщем, надо сделать алгоритм Дейкстры на MPI, но выполнятся он будет не на кластере, а на одном компе.
(далее узел - вычислительный узел)

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

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

Собственно вопрос: если не трудно, поделитесь идеями как это дело можно эффективно распараллелить? И имеет ли вообще смысл распараллеливать поиск из А в В (если не требуется найти путь до всех вершин графа сразу)? Заранее спасибо.

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group