陆毅 崔玉朴 汪坤 姚学勤

摘  要：Dijkstra算法是求解运筹学最短路问题的重要方法之一。文章在分析传统Dijkstra算法思想的基础上寻求其优化途径，发现可以使用堆结构来优化传统算法在查找最小值时重复查找标记的遍历过程。经理论分析与具体实验测试，改进后的算法在时间效率方面明显优于传统算法，提高了该算法的效率和性能，具有较好的适用性。

关键词：最短路径;Dijkstra;堆;运筹学

中图分类号：TP301.6     文献标识码：A文章编号：2096-4706（2021）13-0084-03

The Reaserch on Improvement of Dijkstra Algorithm for Shortest Path Problem in Management Operations Reaserch

LU Yi， CUI Yupu， WANG Kun， YAO Xueqin

（Department of  Management，Wanjiang College of Anhui Normal University， Wuhu  241008， China）

Abstract： Dijkstra algorithm is one of the important methods to solve the shortest path problem in operational research. Based on the analysis of the idea of the traditional Dijkstra algorithm， this paper seeks it’s optimization approach， and finds that the heap structure can be used to optimize the traversal process of the traditional algorithm to repeatedly find the tag when looking for the minimum value. Through theoretical analysis and specific experimental tests， the improved algorithm is significantly better than the traditional algorithm in time efficiency， improves the efficiency and performance of the algorithm， and has good applicability.

Keywords： shortest path; Dijkstra; heap; operations research

0  引  言

最短路径问题是运筹学网络理论中应用最广泛的问题之一，在交通运输、城市规划、物流运输、电子导航等方面都发挥了重要的作用。在实际运用中，如码头集装箱调度、物流运输线路、旅游路径选择等都可以使用这个模型。在求解无负权网络最短路径问题时，目前公认的最好的求解方法是Dijkstra算法，至今仍在广泛运用。近年来随着信息数据的爆发，大规模数据网络最短路径计算的需求大大增加。如导航系统、救援系统都需要在尽可能短的时间内得出合适的路径。这就要求最短路径算法要有更高的效率与性能。

堆是一类数据结构，是维护数据的一个集合。在排序的问题中，可以快速对数据进行排序，时间复杂度为O（logn），并可以以O（1）的时间复杂度获取最小值，时间效率较高。使用堆结构来优化传统算法为获取最小值时重复查找遍历的过程可以减少此过程的运算次数，降低算法的时间复杂度。

在传统Dijkstra算法中，设具有n个顶点与m条边无负权回路的有向图G，算法的时间复杂度为0（n2），当n的规模较大时，算法的时间效率较低，仍具有较大的提升空间。……