Academic Journal of Computing & Information Science, 2022, 5(5); doi: 10.25236/AJCIS.2022.050513.
Heming Bing1, Lu Lai2
1Department of Science, Shenyang Aerospace University, Liaoning, Shenyang, 110136, China
2Department of Mathematics, Xinyu University, Xinyu, Jiangxi, 338004, China
Taking urban express traffic as an example, this paper lists two optimization improvements of Dijkstra algorithm. One is to improve the calculation method of the algorithm to make the calculation more directional, so as to reduce the total amount of calculation. One is in the form of a graphical model, reducing the number of nodes to optimize the calculation process. By comparing the calculation results with the complexity of the traditional algorithm, the effectiveness of the improved method is proved, the complexity of the algorithm is reduced, and the actual work efficiency is improved. It improves the application ability and realizability of Dijkstra algorithm in practical problems.
Dijkstra algorithm; path programming; Optimization and improvement; Application advantages
Heming Bing, Lu Lai. Improvement and Application of Dijkstra Algorithms. Academic Journal of Computing & Information Science (2022), Vol. 5, Issue 5: 97-102. https://doi.org/10.25236/AJCIS.2022.050513.
[1] Dijkstra E W. A Note on two problems in connection with graphs [J]. Nume Mathematik, 1959,1:269-271.
[2] Hongbo Wu, Yingjie Wang, Xiaoxiao Yang. Analysis of Urban Traffic Route Based on Dijkstra Algorithm Optimization [J]. Journal of Beijing Jiaotong University, 2019, 43(04): 116-121+130
[3] Boli Huang. Research on Passenger's Optimal Travel Plan Planning Based on Highway-Rail Multimodal Transport Mode [C]. South China University of Technology, 2020.
[4] Jianqi Lu, Jianguo Nan, Xue Li. Research and Application of Improved Greedy Algorithm in UAV Networking [J]. Journal of Air Force Engineering University (Natural Science Edition), 2020, 21(02): 41-46.
[5] Desheng Feng. Research on Mobile Robot Navigation System Based on ROS [C]. Qilu University of Technology, 2021.
[6] Peng Xu, Gang Cheng, Minyi Li. Dijkstra Optimization and Application of Algorithm in GIS [J]. Beijing Surveying and Mapping, 2021, (06): 737-740.
[7] Wenqing Zheng, Danyang Lu. Dijkstra Research on Algorithm Optimization of Logistics System [J]. Shandong University of Science and Technology, 2018, (05),158-159.
[8] Dujuan Huang, Tianyuan Zhang. Research on Township Location Selection of Smart Express Cabinet Based on Dijkstra Algorithm [J]. Journal of Liaoning University of Technology (Natural Science Edition), 2020, 40(04): 259-263.
[9] Bandy JA, Marty USR. Graph Theory with Applications. New York: The Macmillan Press ltd.1976. 1-22.
[10] Wenxiong Kang, Yaozhao Xu. Hierarchical Dijkstra Algorithm for Node-constrained Shortest Path [J]. Journal of South China University of Technology (Natural Science Edition), 2017, 45(01): 66-73.
[11] Luyu Lan. Research on Urban Road Congestion Relief Method Based on Multiple Shortest Paths [C]. Shenzhen University, 2018.
[12] T. A. J. Nicholson. Finding the Shortest Route between Two Points in a Network. The Computer Journal, 1966, 9 (3), 275-280.