如何执行使用OpenMP/MPI的并行化Dijkstra算法

Question

我正在尝试为课程项目实现Dijkstra算法的并行版本（我的第一个并行算法）。我使用优先级队列顺序地完成了顺序部分，没有问题，但我很难弄清楚如何设计一个并行版本。到目前为止，我一直在使用this作为参考。我不是要求任何人为我设计整个事情，只是向我提供一些关于如何实施的见解或好的建议。我一直在考虑这些东西到目前为止：

• OpenMP，MPI或两者兼而有之？
• PCAM？ （例如图分区）
• 共享内存？

Answer 1

试试这个演示的想法：

http://www.cse.buffalo.edu/faculty/miller/Courses/CSE633/Ye-Fall-2012-CSE633.pdf