Extended Dijkstra Algorithm and Moore-Bellman-Ford Algorithm

Digital Technologies Research and Applications

Article

Extended Dijkstra Algorithm and Moore-Bellman-Ford Algorithm

Downloads

https://doi.org/10.54963/dtra.v5i1.1787
Cheng, C. (2026). Extended Dijkstra Algorithm and Moore-Bellman-Ford Algorithm. Digital Technologies Research and Applications, 5(1), 178–192. https://doi.org/10.54963/dtra.v5i1.1787
Volume 5 Issue 1: March 2026 (in progress)
Copyright (c) 2026 Congdian Cheng
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright

The authors shall retain the copyright of their work but allow the Publisher to publish, copy, distribute, and convey the work.

License

Digital Technologies Research and Applications (DTRA)  publishes accepted manuscripts under Creative Commons Attribution 4.0 International (CC BY 4.0). Authors who submit their papers for publication by DTRA agree to have the CC BY 4.0 license applied to their work, and that anyone is allowed to reuse the article or part of it free of charge for any purpose, including commercial use. As long as the author and original source are properly cited, anyone may copy, redistribute, reuse, and transform the content.

Authors

  • Congdian Cheng

    School of Intelligence Technology, Geely University of China, Chengdu 641400, China

Received: 29 October 2025; Revised: 25 November 2025; Accepted: 24 December 2025; Published: 12 February 2026

The shortest path problem which can not be solved by classical Dijkstra algorithm and Moore-Bellman-Ford algorithm appears frequently, for example, the Anti-risk Path Problem proposed by Xiao et al. To address this kind of shortest path problem, the present work proposes and studies a general single-source shortest path problem, which is motivated by current interest in needing to extend the total weight function of paths on a network and the classical shortest path problem. Firstly, define the path functional on a set of certain paths with same source on a graph; introduce a few concepts of the defined path functional; and make some discussions on the properties of the path functional. Secondly, develop a kind of general single-source shortest path problem (GSSSP). Thirdly, following respectively the approaches of the well known Dijkstra’s algorithm and Moore-Bellman-Ford algorithm, design an extended Dijkstra’s algorithm (EDA) and an extended Moore-Bellman-Ford algorithm (EMBFA) to solve the problem GSSSP under certain given conditions. Fourthly, under the assumption that the value of related path functional for any path can be obtained in M(n) time, prove respectively the algorithm EDA solving the problem GSSSP in O(n2)M(n) time and the algorithm EMBFA solving the problem GSSSP in O(mn)M(n) time. Finally, some applications of the designed algorithms are shown with a few examples. What we done can not only improve both the researches and the applications of the shortest path theory, but also promote the development of the researches and the applications of other combinatorial optimization problems, promote the development of the algorithm theory and promote the development of the artificial intelligence.

Keywords:

Graph Network Path Functional Shortest Path Algorithm

References

  1. Korte, B.; Vygen, J. Combinatorial Optimization: Theory and Algorithms; Springer-Verlag: Berlin, Germany, 2000.
  2. Bellman, R.E. On a Routing Problem. Q. Appl. Math. 1958, 16, 87–90.
  3. Dijkstra, E.W. A Note on Two Problems in Connexion with Graphs. Numer. Math. 1959, 1, 269–271.
  4. Ford Jr., L.R. Network Flow Theory; The Rand Corporation: Santa Monica, CA, USA, 1956.
  5. Moore, E.F. The Shortest Path through a Maze. In Proceedings of the International Symposium on the Theory of Switching, Part II; Harvard University Press: Cambridge, MA, USA, 1959; pp. 285–292.
  6. Hershberger, J.; Suri, S. Vickrey Prices and Shortest Paths: What Is an Edge Worth? In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science; Computer Society: Las Vegas, NV, USA, 2001; pp. 252–259.
  7. Hershberger, J.; Suri, S.; Bhosle, A. On the Difficulty of Some Shortest Path Problems. In Lecture Notes in Computer Science; Springer: Berlin, Germany, 2003; pp. 343–354.
  8. Cho, H.J.; Lan, C.L.; Simos, T.E.; et al. A Hybrid Shortest Path Algorithm for Navigation System. AIP Conf. Proc. 2007, 963, 1073–1076. DOI: https://doi.org/10.1063/1.2835913
  9. Du, D.Z.; Graham, R.L.; Pardalos, P.M.; et al. Analysis of Greedy Approximations with Nonsubmodular Potential Functions. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 20–22 January 2008; pp. 167–175.
  10. Xiao, P.; Xu, Y.; Su, B. Finding an Anti-Risk Path between Two Nodes in Undirected Graphs. J. Comb. Optim. 2009, 17, 235–246.
  11. Mahadeokar, J.; Saxena, S. Faster Algorithm to Find Anti-Risk Path between Two Nodes of an Undirected Graph. J. Comb. Optim. 2014, 27, 798–807. DOI: https://doi.org/10.1007/s10878-012-9553-0
  12. Srivastava, K.; Tyagi, R. Shortest Path Algorithm for Satellite Network. Int. J. Innov. Res. Dev. 2013, 5, 438–445.
  13. Murota, K.; Shioura, A. Dijkstra's Algorithm and L-Concave Function Maximization. Math. Program. Ser. A 2014, 145, 163–177. DOI: https://doi.org/10.1007/s10107-013-0643-2
  14. Feng, G. Finding k Shortest Simple Paths in Directed Graphs: A Node Classification Algorithm. Networks 2014, 63, 6–17. DOI: https://doi.org/10.1002/net.21552
  15. Zhang, H.L.; Xu, Y.F.; Wen, X.G. Optimal Shortest Path Set Problem in Undirected Graphs. J. Comb. Optim. 2015, 29, 511–530. DOI: https://doi.org/10.1007/s10878-014-9766-5
  16. Nip, K.; Wang, Z.; Nobibon, F.T.; et al. A Combination of Flow Shop Scheduling and the Shortest Path Problem. J. Comb. Optim. 2015, 29, 36–52. DOI: https://doi.org/10.1007/s10878-013-9670-4
  17. Meng, S.C.Y.; Adnan, N.; Sukri, S.S.; et al. An Experiment on the Performance of Shortest Path Algorithm. In Proceedings of the Knowledge Management International Conference, Chiang Mai, Thailand, 29–30 August 2016; pp. 7–12.
  18. Dinitz, Y.; Itzhak, R. Hybrid Bellman-Ford-Dijkstra Algorithm. J. Discrete Algorithms 2017, 42, 35–44. DOI: https://doi.org/10.1016/j.jda.2017.01.001
  19. AbuSalim, S.W.G.; Ibrahim, R.; Saringat, M.Z.; et al. Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization. In Proceedings of the IOP Conference Series: Materials Science and Engineering, Penang, Malaysia, 17–18 April 2020; pp. 1–11. DOI: https://doi.org/10.1088/1757-899X/917/1/012077
  20. Xia, D.W.; Shen, B.Q.; Zheng, Y.L.; et al. A Bidirectional A-Star-Based Ant Colony Optimization Algorithm for Big-Data-Driven Taxi Route Recommendation. Multimed. Tools Appl. 2024, 83, 16313–16335. DOI: https://doi.org/10.1007/s11042-023-15498-4
  21. Gajjar, K.; Jha, A.V.; Kumar, M.; et al. Reconfiguring Shortest Paths in Graphs. Algorithmica 2024, 86, 3309–3338. DOI: https://doi.org/10.1007/s00453-024-01263-y
  22. Wu, H.C. Bernstein Approximations for Fuzzy-Valued Functions. Mathematics 2025, 13, 2424. DOI: https://doi.org/10.3390/math13152424
  23. Xu, D.K.; Tian, R.Q.; Lu, Y. Bayesian Adaptive Lasso for the Partial Functional Linear Spatial Autoregressive Model. J. Math. 2022, 1616068. DOI: https://doi.org/10.1155/2022/1616068
  24. Bäusing, C.; John, D.; Mathwieser, C. Precedence-Constrained Shortest Path. Networks 2025, 86, 282–295. DOI: https://doi.org/10.1002/net.22282
  25. Deen, M.R.Z.E.; Aboamer, W.A.; El-Sherbiny, H.M. Explicit Formulas for the Complexity of Networks Produced by New Duplicating Corona and Cartesian Product. J. Math. 2024, 9131329. DOI: https://doi.org/10.1155/2024/9131329
  26. Henke, D.; Wulf, L. On the Complexity of the Bilevel Shortest Path Problem. Networks 2025, 86, 428–445. DOI: https://doi.org/10.1002/net.70002
  27. Hooshmand, M.K.; Huchaiah, M.D. Network Intrusion Detection with 1D Convolutional Neural Networks. Digit. Technol. Res. Appl. 2022, 1, 66–75.
  28. Kovács, L. Classification Improvement with Integration of Radial Basis Function and Multilayer Perceptron Network Architectures. Mathematics 2025, 13, 1471. DOI: https://doi.org/10.3390/math13091471
  29. Acuña, E.G.A.; Doriano, S.C.; Salgado, F. Quantum-Enhanced Cognitive Modeling for Advanced Logistics Route Optimization. Digit. Technol. Res. Appl. 2025, 4, 61–84.
  30. Mao, Z.; Yang, Z.; Luo, D.; et al. A Multi-Strategy Enhanced Dung Beetle Algorithm for Solving Real-World Engineering Problems. Artif. Intell. Rev. 2025, 58, 253. DOI: https://doi.org/10.1007/s10462-025-11235-5
  31. Jahanmanesh, P.; Farhadi, A.; Zamanifar, A. Mobility Management with AI. IEEE Access 2025, 13, 83022–83060. DOI: https://doi.org/10.1109/ACCESS.2025.3566337
  32. Razavi, S.M.; Tran, T.M.; Wilson, S.E.; et al. Brain State Transition Disruptions in Alzheimer's Disease: Insights from EEG State Dynamics. In Proceedings of the IEEE International Symposium on Biomedical Imaging, Seoul, Republic of Korea, 2 December 2025.
  33. Saghezchi, A.; Kashani, V.G.; Ghodratizadeh, F. A Comprehensive Optimization Approach on Financial Resource Allocation in Scale-Ups. J. Bus. Manag. Stud. 2024, 6, 62–75. DOI: https://doi.org/10.32996/jbms.2024.6.6.5