Design and implementation of parallel shortest path search algorithm
Lu Zhao, Jun Shi · Computer Engineering and Applications Journal · 2010
In view of the serial search for the shortest path algorithm inherent limitations and the difficult to raising the issue of search speed as the size of the network increases,the parallel shortest path search algorithm is designed and implemented based on the parallel Dijkstra's algorithm idea.The complexity of the algorithm reduces to O(N2/p+N*(p-1)) as compared with the complexity O(N2) of serial Dijkstra's algorithm.Experimental results show that the parallel shortest path search algorithm has fast and stable performance.The algorithm has better performance when the network contains a substantial number of nodes.