关键词: Dijkstra算法, 并行计算, 最短路径, 正则树, 时间复杂度, 仿真实验

Abstract:

In order to make optimized to Dijkstra algorithm, this paper gives a proof of multi-label Dijkstra algorithm and uses it as a fundamentals to make the optimized improvement, which is the classical Dijkstra algorithm and the multi-label Dijkstra algorithm with serial and parallel way. Facing the regular graph, this paper calculates three algorithm time complexity. After analysis, this paper comes up with multi-label parallel computing for the Dijkstra optimized algorithm. This optimized algorithm designs four experiment to verify degree of optimization by running time and parallel acceleration ratio. The experiment result shows the multi-label parallel computing algorithm is more effective than the classical Dijkstra algorithm and the multi-label serial computing algorithm facing the dense graph which point number are more than 6 000 and sparse graph（regular tree）. For the regular tree, it exists positive correlation between the effectiveness and regular tree’s depth and out degree.

Key words: Dijkstra algorithm, parallel compute, shortest path, regular tree, time complexity；simulation experiment