Parallel Shortest Path Algorithm Based on Vertex Cut-set
Wen Shen · Journal of Zhengzhou University · 2012
In this paper,research and analysis on the basis of the Dijkstra algorithm,the Dijkstra algorithm by introducing the vertex of cut sets and cut the vertex of idea to improve the Dijkstra algorithm,this method first vertex cut-set or cut vertex to the original problem is decomposed into multiple sub-graph,then the shortest path on each sub-graph parallel to the shortest path of the original problem,and finally obtained by the vertex cut-set or cut vertex,which reduces the time complexity of the algorithm and improves the efficiency of the algorithm.