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

摘要：

通过分析经典Dijkstra算法的思想和执行流程，对多标号的Dijkstra算法给出新证明，以此作为理论依据对Dijkstra算法进行了多标号的串行与并行优化。对于正则树，给出了经典Dijkstra算法、串行多标号Dijkstra算法和并行多标号Dijkstra算法的时间复杂度排序。针对优化算法的特点，设计出四种实验，采用运行时间和并行加速比作为优化指标，考核三种算法的效率。仿真实验表明：对顶点数大于6 000的稠密图和稀疏图（正则树），多标号并行算法优于串行算法，且优化效果明显；对于正则树，优化效果分别与深度、出度成正相关。

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