Dijkstra算法优化综述

开篇：润墨网以专业的文秘视角，为您筛选了一篇Dijkstra算法优化综述范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘 要】文章简述了dijkstra经典算法的提出及应用，讨论了算法的基本原理及不足之处。列举了国内外对Dijkstra经典算法的优化进展，同时列举了其应用领域，指出进一步的研究方向，为Dijkstra经典算法优化的相关研究提供参考。

【关键词】Dijkstra算法；优化

【Abstract】The papaer described the application of the classical Dijkstra algorithm and discussed the basic prnciple and shortcomings of algorithm. Listing the progress of optimization of the classical algorithm Dijkstra at home and abroad and its application field and pointing out rhe directions for the further study， providing a reference for the related research of classical Dijkstra algorithm.

【Key words】Dijkstra algorithm， optimization

1 引言

Dijkstra经典算法是由计算机科学家Edsger Dijkstra在文献中提出的。它是一个图的搜索算法，解决带非负权重图的单元最短路径问题并产生一棵最短路径树。该算法经常使用在网络路由和地理信息系统中。

2 Dijkstra算法原理

（1）算法分配给每个节点一个初步的距离值：设置初始节点为零和其他节点为无穷；

（2）将当前访问节点设置为初始节点，其他的所有节点设置为未访问节点，并创建一个未访问节点集合；

（3）针对当前节点，计算其与所有邻接节点的距离。将计算出来的距离值与当前值进行比较，指定较小的一个。

（4）当我们考虑完当前节点的所有邻接节点，标记当前为已访问，并将其从未访问集合删除。已访问节点将永远不会被访问；

（5）选择为访问过的标记最小试探距离的节点，并将其作为新的当前节点，然后回到步骤3；

（6）如果终止节点已标记访问或者最小试探性距离在未设置节点之间是无限的，该算法已完成。

3 Dijkstra算法优化

在Dijkstra算法中，一般采用一个可更新排序的优先队列来实现对已经计算过距离中距离最小的节点。因此，如何实现Dijkstra算法的优先队列结构，就成为提高Dijkstra算法性能的关键。

Dijkstra算法的优先队列需要进行INSERT（插入）、EXTRACT-MIN（调整最小）、DECREASE-KEY（降级）三个基本操作。对于图（V，E），经典Dijkstra算法每次INSERT和DECREASE-KEY操作的执行时间为O（1），每次EXTRACT-MIN的操作时间为O（V）（因为需要搜索整个为访问节点数组），算法的总运行时间为O（V2+E）= O（V2）。

由Donald B. Johnson 在文献提出来采用的d-堆每个节点有d个儿子，这使得插入和降级操作的时间复杂度改进为O（logdV），但调整最小的时间复杂度只提高到O（dlogdV）。因此，它在最好情况下可以把Dijkstra算法的时间复杂度提高到O（Elog（2+（E/V）V）。

由Michael L. Fredman，Robert Endre Tarjan 在文献提出的斐波那契堆，使得插入操作时间复杂度为O（1），降级的摊还时间复杂度为O（1），调整最小的摊还时间复杂度为O（logV），Dijkstra算法的时间复杂度为O（E+VlogV）。

由Henzinger MR，Rao S，Subramanian S，Klein P在文献提出来采用二叉堆的优先队列的所有操作时间复杂度为O（logV），Dijkstra算法的时间复杂度为O（ElogV）。

由于经典Dijkstra算法在每次迭代中都需要扫描所有未标记节点，面对海量的数据，算法执行效率非常低。因此单单只通过上述优化数据结构已经不够，还需要减少搜索量。

这方面的优化有：（1）使用评估函数来接近目标地节点；（2）利用当前目标地之间的夹角关系，使当前节点趋向于目标节点；（3）用限制区域来减少遍历节点；（4）处理交汇路径减少搜索路径。这些优化方法有的利用特定信息，有的则是在特殊情况下的优化效果明显。因此，今后的优化方向应当在优化经典Dijkstra算法结构的同时，根据数据的不同情况进行细分，期望达到最优。

4 结束语

Dijkstra算法是求单源最短路径的经典算法，主要应用于网络路由和地理信息系统的最优路径求解。但是，随着数据的海量式增长，经典Dijkstra算法的运行效率已经无法人们的需求，满足需要从各方面进行优化。本文给出了国内外研究Dijkstra算法的主要研究方向，通过对比总结出今后优化的方向，希望对广大研究人员有参考意义。

参考文献：

[1]E. W. Dijkstra. A note on two problems in connexion with graphs [J]. Numerische Mathematik， 1959.

[2]Donald B. Johnson.Priority queues with update and finding minimum spanning trees [J].Information Processing Letters， 1975.

[3]Michael L. Fredman，Robert Endre Tarjan [J]. Journal of the ACM， 1987.

[4]Henzinger MR，Rao S，Subramanian S，Klein P.Faster shortest-path algorithms for planar graphs [J].Journal of Computer and System Sciences， 1997.

[5]Robert Sedgewick ，Jeffrey Scott Vitter. Shortest paths in euclidean graphs[J].Algorithmica， 1986.

[6]严寒冰，刘迎春. 基于GIS的城市道路网最短路径算法探讨[J]. 计算机学报， 2000.

[7]卢冬梅，崔伟宏. 交通网络限制搜索区域时间最短路径算法[J]. 中国图像图形学报， 1999.

[8]刘刚，李永树，杨骏. 一种Dijkstra算法改进方法的研究与实现[J]. 测绘科学，2011.