Dijkstra's algorithms performs well sequentially. However, applications require even better parallel performance because of real-time constraints. Implementations such as SprayList and Relaxed Queues allow parallelism on priority queue operations in Dijkstra's algorithm, with various performance vs accuracy tradeoffs. Which of these algorithms is the best in terms of raw parallel performance?
Check this information
https://cse.buffalo.edu/faculty/miller/Courses/CSE633/Ye-Fall-2012-CSE633.pdf
Given a weighted, directed graph, the all-pairs shortest-path problem is to find the length of the shortest path between every pair of vertices.
More than 40 years ago Floyd invented an O(n3) time algorithm for solving the all-pairs shortest-path problem.
In the book "Parallel Programming in C with MPI and OpenMP", Michael J. Quinn.
McGraw-Hill Education Group ©2003
ISBN:0071232656
In the chapter 6, you have a parallel version of this algorithm.
I don't know if it is the best parallel version to calculate the minimum distance between all pairs of nodes in a network. You will have to try it.
Bye.
Check this information
https://cse.buffalo.edu/faculty/miller/Courses/CSE633/Ye-Fall-2012-CSE633.pdf
Erik's reference is important to demonstrate that speedup can be decreasing because of communication latency. A more recent publication claims to reduce communication overhead:
Saeed Maleki, Donald Nguyen, Andrew Lenharth, María Garzarán, David Padua, and Keshav Pingali. 2016. DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem. In Proceedings of the 2016 International Conference on Supercomputing (ICS '16). ACM, New York, NY, USA, Article 32, DOI: https://doi.org/10.1145/2925426.2926287
Regards,
Frank
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs