A parallel Dijkstra algorithm based on multi-granularity communication

作者：Sun Wenbin^*; Tan Zhenglong; Wang Jiang; Zhao Shuaiyang

来源：Journal of China University of Mining & Technology, 2014, 43(5): 938-943.

• Bi-directional search
• Communication method
• Communication time
• Dijkstra algorithms
• MPI communications
• Network segmentation
• Parallelization algorithms
• Shortest path algorithms

Parallelizing serial algorithm is one of effective methods to improve shortest path algorithm efficiency. A new parallel method based on the idea of bidirectional search and overlapping network segmentation is approached in this paper. In order to reduce communication time of shortest path algorithm, a multi-granularity communication method among different processes is described. The experiment is done by using of American road network data provided by DIMAS. The result indicates: overlapping network segmentation method is an effective selection for shortest path algorithm; improving communication multi-granularity size reduces communication time of different processes in parallelization algorithm; MPI communication time by transferring 50 network nodes each time is one-tenth of that by transferring 1 network node.

• 出版日期2014
• 单位中国矿业大学（北京）