Dijkstra算法的优化

The Optimization of Dijkstra Algorithm

Dijkstra算法是许多工程解决最短路径问题的理论基础,可用来找出图中指定节点到其他节点的最短距离,有着广泛的应用。文章通过分析传统Dijkstra算法的设计思想,提出该算法在实现方法上存在的一些不足之处,并从节约存储空间和提高运算效率方面对其进行了改进,并通过复杂性分析比较,得出这种改进算法的效率优于传统的Dijkstra算法。

Dijkstra algorithm is used to find the shortest path between various nodes at the right value in a given graph.In many projects it serves as the rationale for solving the shortest path problem.On the basis of an analysis of traditional Dijkstra algorithm＇s design philosophy,the paper presents some of its defects in implementation and puts forward some suggestions for improvement for the purpose of saving memory space and increasing efficiency.Furthermore,by comparison of their complexity analysis,it proves that the improved algorithm is superior to the traditional one in efficiency.