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
相关论文
共 50 条
  • [31] Multi-dimension and multi-granularity segmentation of remote sensing image based on improved Otsu algorithm
    Huang, Dongmei
    Sun, Jingqi
    Liu, Shuang
    Xu, Shoujue
    Liang, Suling
    Li, Cong
    Wang, Zhenhua
    PROCEEDINGS OF THE 2017 IEEE 14TH INTERNATIONAL CONFERENCE ON NETWORKING, SENSING AND CONTROL (ICNSC 2017), 2017, : 679 - 684
  • [32] Multi-granularity Rough Set and Measure Based on Weighted Granularity on the Dual Universes
    Peng Liangui
    Yan Ruixia
    Chen Zhaojun
    PROCEEDINGS OF THE 30TH CHINESE CONTROL AND DECISION CONFERENCE (2018 CCDC), 2018, : 1761 - 1765
  • [33] Automatic classification of multi-source and multi-granularity teaching resources based on random forest algorithm
    Li, Dahui
    Qu, Peng
    Jin, Tao
    Chen, Changchun
    Bai, Yunfei
    INTERNATIONAL JOURNAL OF CONTINUING ENGINEERING EDUCATION AND LIFE-LONG LEARNING, 2023, 33 (2-3) : 177 - 191
  • [34] Cloud Service Composition Based on Multi-Granularity Clustering
    Cai, Huihui
    Cui, Lizhen
    JOURNAL OF ALGORITHMS & COMPUTATIONAL TECHNOLOGY, 2014, 8 (02) : 143 - 161
  • [35] Learning multi-granularity features from multi-granularity regions for person re-identification
    Yang, Kaiwen
    Yang, Jiwei
    Tian, Xinmei
    NEUROCOMPUTING, 2021, 432 : 206 - 215
  • [36] Multi-granularity User Portrait Based on Granular Computing
    Jiang M.
    Miao D.
    Luo S.
    Zhao C.
    Moshi Shibie yu Rengong Zhineng/Pattern Recognition and Artificial Intelligence, 2019, 32 (08): : 691 - 698
  • [37] Multi-granularity relabeled under-sampling algorithm for imbalanced data
    Dai, Qi
    Liu, Jian-wei
    Liu, Yang
    APPLIED SOFT COMPUTING, 2022, 124
  • [38] MgdFlow: multi-granularity data flow management algorithm in microgrid scenario
    Jing Y.
    Cao Q.
    Zhu R.
    Tongxin Xuebao/Journal on Communications, 2023, 44 (10): : 94 - 102
  • [39] Study on Similarity Algorithm of Multi-Granularity Spatio Temporal Event Sequences
    Wang C.
    Huang L.
    Zhao K.
    Beijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology, 2021, 41 (01): : 102 - 111
  • [40] A new multi-granularity grooming algorithm based on traffic partition in IP over WDM networks
    Wang, Xingwei
    Hou, Weigang
    Guo, Lei
    Cao, Jiannong
    Jiang, Dingde
    COMPUTER NETWORKS, 2011, 55 (03) : 807 - 821
12345