How to go about implementing a parallelized Dijkstra's algorithm using OpenMP/MPI

Question

I'm trying to implement a parallelized version of Dijkstra's algorithm (my very first parallel algorithm) for a course project. I got the sequential part down using a priority queue with no problem, but I'm having trouble figuring out how to go about designing a parallel version. I've been using this as a reference so far. I'm not asking anyone to design the whole thing for me, just offer me some insights or good advice about how to go about the implementation. I've been considering these things so far:

• OpenMP, MPI or both?
• PCAM? (e.g. graph partitioning)
• Shared memory?

Answer 1

Try this presentation for ideas:

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