Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity

Abstract

Optimization is the process of obtaining the most appropriate solution for a specific purpose and within the constraints given. In mathematical sense, it can be expressed as minimizing or maximizing a function. In this study, one of the optimization problems, the shortest path problem, is discussed. Classical and heuristic algorithms developed for solving shortest path problems are widely used. In this study, from the classical algorithms, Dijkstra, Bellman Ford, Johnson algorithms and from heuristic algorithms, Genetic, Scaling and Dinitz algorithms are examined. In this context, the complexities of the algorithms were investigated and comparisons were made. The results obtained from the examinations are presented with tables and graphs.

Keywords

• Optimization
• shortest path problems
• Classic algorithm
• Heuristic algorithms
• Complexity

References

1. [1] Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity, Creative Commons, California, USA, 2006.
2. [2] Broumi, S., Bakali, A., Talea, M., Smarandache, F., Vladareanu, L., Computation of Shortest Path Problem in a Network with SV-Trapezoidal Neutrosophic Numbers, International Conference on Advanced Mechatronic Systems, Melbourne, Australia, 2016, 417–422.
3. [3] Chabrier, A., Vehicle Routing Problem with Elementary Shortest Path Based Column Generation, Computers and Operations Research, vol:33 (2006), 2972–2990.
4. [4] Cömert, Z., En Kısa Yol Problemi, Bilişim: Paylas¸ım, 2015, 1–6.
5. [5] Çetinkaya, C.P., Engin, A., Su Kalitesi Gözlem Ağlarında Örnekleme için İzlenecek Yol Rotası Optimizasyonuna Bir Yaklas¸ım ve Gediz Havzasına Uygulanması, AKU FEMUBID, vol:18 (2018), 265–275.
6. [6] Çunkas¸, M., Genetik Algoritmalar ve Uygulamaları, Selcuk Universitesi Ders Notları, 2006.
7. [7] Dinitz, Y., Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Springer, 2006.
8. [8] Duchon, F., Babinec, A., Kajan, M., Beno, P., Florek, M., Fico, T., Jurisica, L., Path Planning with Modified A Star Algorithm for a Mobile Robot, Procedia Engineering, vol:96 (2014), 59–69.

9. [9] Edmonds, J., Karp, R.M., Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, vol:19 (1972), 248–264.
10. [10] Friis, J.M., Olesen, S.B.,An Experimental Comparison of Max Flow Algorithms, Aarhus University, Master Thesis, 2014.
11. [11] Gabow, H.N., Scaling Algorithms for Network Problems, Journal of Computer and System Sciences, vol:31(1985), 148–168.
12. [12] Gonen, B., Louis, S.J., Genetic Algorithm Finding the Shortest Path in Networks, International Conference on Genetic and Evolutionary Methods, Nevada, USA, 2011, 1–4.
13. [13] Gupta, A., Shortest Paths and Seidel’s Algorithm, CMU, Lecture 4, 2017, 1–10.
14. [14] Medhi, D., Ramasamy, K., Network Routing: Algorithms, Protocols, and Architectures, Morgan Kaufmann Publishers, San Francisco, CA, 2007.
15. [15] Nazari, S., Meybodi, M.R., Salehi, M.A., Taghipour, S., An Advanced Algorithm for Finding Shortest Path in Car Navigation System, First International Conference on Intelligent Networks and Intelligent Systems, Wuhan, China, 2008, 671–674.
16. [16] Ozturk, A., Yoneylem Arastırması, Ekin Kitabevi, Bursa, Turkey, 2001.
17. [17] Siyah, B., Genetik Algoritma Kullanılarak Noktadan Noktaya Yol ve Rota Planlama, Software Engineer in Deep Learning, WordPress, 2014.
18. [18] Soltani, A.R., Tawfik, H., Goulermas, Y.J., Fernando, T., Path Planning in Construction Sites: Performance Evaluation of the Dijkstra, A* and GA Search Algorithms, Advanced Engineering Informatics, vol:16 (2002), 291–303.
19. [19] Tastan, O., Temizel, A.,Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU, Ulusal Y¨uksek Bas¸arımlı Hesaplama Konferansı, ˙Istanbul, Turkey, 2017, 1–6.
20. [20] Ucan, F., Kaplan, G.B., Çaputçu, R., Haklıdır, M., Arar, Ö. F., Taktiksel En Kısa Yol Problemlerinin Genetik Algoritma Yaklas¸ımı ile C¸ o¨ z u¨ mu¨, USMOS, Ankara, Turkey, 2007, 326–336.
21. [21] Yurtay, N., Ayrık Işlemsel Yapılar, Sakarya U¨ niversitesi Ders Notları, 2008, 14–20.