A parallel Dijkstra algorithm based on multi-granularity communication

被引：0

作者：

Sun, Wenbin ^{[1
]}

Tan, Zhenglong ^{[1
]}

Wang, Jiang ^{[1
]}

Zhao, Shuaiyang ^{[1
]}

机构：

[1] School of Geoscience and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing,100083, China

来源：

Zhongguo Kuangye Daxue Xuebao/Journal of China University of Mining and Technology | 2014年 / 43卷 / 05期

关键词：

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

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：938 / 943