Parallel implementation of finding the shortest path using MPI

Question

Algorithms

Hello. Actually, you need to organize a parallel calculation of the shortest path using MPI, and it will be performed on one machine. You can use the Floyd or Dijkstra algorithm. In this regard, I have been racking my brains for three days about how to do this, so to speak, in the spirit of MPI, but I have not come up with anything sensible. In general, it seems to me that it is difficult to divide such a task into independent parts, so all the time I want to somehow use multithreading and shared memory. Therefore, the following questions arose:
- is it worth trying to organize a shared memory between processes, in which the adjacency matrix would be stored, or is it better to still use messaging between processes?
- How is common memory usually organized for computing nodes in clusters, and is it difficult?
PS:While googling on this issue, I met such thoughts that "in a well-paralleled application, a small fraction of the time is spent on the actual interaction between branches (data transfers and synchronization)" or "barriers are not required in a well-paralleled algorithm." Do you think Floyd or Dijkstra can be "well parallelized"?
PPS: Naturally, the answer to all these questions will take a lot of time and space, so I will be glad if you recommend good books on this topic (preferably in Russian).
Thanks in advance

Answer 1

Required MPI? Not MPI2? MPI2 has operations designed to work quickly on top of shared memory.