Research On The Single-source Shortest Path Parallel Algorithms Based On The Parallel Boost Graph Library

The single-source shortest path problem as to the main optimal routing problem is the basis of the most optimal problems in many social application areas. With the continuous expansion of social information, the amount of data from the shortest path problem is very large, so both the computing time and the storage space increase significantly. Therefore, in order to meet the strict requirements of the faster computational efficiency and the larger storage space, the shortest path problem can be solved by means of parallel computing technology, which uses the parallel computer to provide enough memory and computing power, and develops the good parallel algorithm in accordance with the parallel computing model to save greatly the time for solving the shortest path problem.The paper discusses the two different single-source shortest path serial algorithms in term of the implementation technique: Dijkstra algorithm based on labeling setting and BFM algorithm based on labeling correcting. Meanwhile, combining these two ideas, we propose a new kind of single-source shortest path algorithm based on bucket structure, which has good time complexity and parallelism property.Then, the paper studies thoroughly module components and functional approach of parallel Boost graph library. According to the general parallel implementation framework and basic ideas in the parallel Boost graph library of Dijkstra algorithm and the BFM algorithm, we propose corresponding improvement methods, which have good parallel speedup ratio and scalability.In addition, this paper focuses on the proposed bucket structure, using a direct parallel method for parallel algorithm design and distributed data structures and communication mechanisms of parallel Boost graph library, to design and implement single-source shortest path parallel algorithm on the distributed parallel cluster computer. We design bucket structure based on bucket width parameter, the optimum storage based on graph partition, asynchronous parallel communication strategy and a smaller message transmission pack to make parallel algorithm solve different data sizes and structure characters of the single-source shortest path problem, which have good parallel speedup ratio and scalability.