An Analysis of Parallelizing Shortest Path Algorithm

Familiar parallelization shortest path algorithms focus on single source multiple sinks or multiple sources multiple sinks problems,but less is capable to query shortest path of single source single sink problem.Parallelizing shortest path methods based on parallelization Boost library,network partition and bidirectional search are approached in this paper.An experiment using road network data on DIMAS is done.The result indicates that bidirectional search parallelization algorithm is effective and consuming time of this algorithm is twenty-five to fifty percent of serial Dijkstra algorithm.