基于点割集的并行最短路径算法

Parallel Shortest Path Algorithm Based on Vertex Cut-set

在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.

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 al- gorithm.