摘 要：Dijkstra 算法是求解运筹学最短路问题的重要方法之一。文章在分析传统 Dijkstra 算法思想的基础上寻求其优化途径，发现可以使用堆结构来优化传统算法在查找最小值时重复查找标记的遍历过程。经理论分析与具体实验测试，改进后的算法在时间效率方面明显优于传统算法，提高了该算法的效率和性能，具有较好的适用性。
关键词：最短路径；Dijkstra；堆；运筹学
DOI:10.19850/j.cnki.2096-4706.2021.13.021
中图分类号：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
参考文献：
[1] 张翰林，关爱薇，傅珂，等 .Dijkstra 最短路径算法的堆 优化实验研究 [J]. 软件，2017，38（5）：15-21.
[2] 王志和，凌云 .Dijkstra 最短路径算法的优化及其实现 [J]. 微计算机信息，2007，（33）：275-277.
[3] 邱慧，黄解宇，黄丽丹 . 管理运筹学中最短路问题的两种 算法研究 [J]. 运城学院学报，2014，32（2）：89-91.
[4] 严蔚敏，吴伟民 . 数据结构（C 语言版） [M]. 北京：清 华大学出版社，2002.
[5] 李健 . 基于 Dijkstra 最短路径算法的优化研究 [J]. 渭南师 范学院学报，2009，24（5）：61-64.
[6] 韩伟一 . 基于固定序的 Bellman-Ford 算法的改进 [J]. 运 筹与管理，2015，24（4）：111-115.
[7] DIJKSTRA E W. A note on two problems in connexion with graphs [J].Numerical Mathematics，1959，1（1）：269-271.
[8] 胡运权，郭耀煌 . 运筹学教程 [M]. 北京：清华大学出版社， 1998.
[9] 曲大鹏，侯振桓，宣伟宏，等 . 最小生成树相关算法在计 算机程序设计竞赛中的研究 [J]. 辽宁大学学报（自然科学版）， 2020，47（2）：118-123.
作者简介：陆毅（2000—），男，汉族，安徽蚌埠人，本科在 读，研究方向：运筹学。