A Parallel Single-Source Shortest Path Algorithm based on Bucket Structure

This paper focuses on the proposed bucket structure, using communication mechanisms and data structures of Parallel Boost Graph Library and parallel algorithm design method, to propose a parallel single-source shortest path algorithm based on bucket structure. In this algorithm, bucket structure is designed by bucket width parameter, the storage structure is designed by graph partition, information packets are transmitted by asynchronous parallel communication strategy, which makes our algorithm has good parallel speedup ratio and scalability in solving all the single-source shortest path problems. At last the conclusions are verified by experiments.