Параллельная реализация алгоритма Дейкстры [MPI]

[Perzh]

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

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

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

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