Research Article
BibTex RIS Cite

Year 2020, Volume: 8 Issue: 2, 279 - 283, 27.10.2020

Öznur İşçi Güneri Burcu Durmuş

Abstract

References

  • [1] Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity, Creative Commons, California, USA, 2006.
  • [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] Chabrier, A., Vehicle Routing Problem with Elementary Shortest Path Based Column Generation, Computers and Operations Research, vol:33 (2006), 2972–2990.
  • [4] Cömert, Z., En Kısa Yol Problemi, Bilişim: Paylas¸ım, 2015, 1–6.
  • [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] Çunkas¸, M., Genetik Algoritmalar ve Uygulamaları, Selcuk Universitesi Ders Notları, 2006.
  • [7] Dinitz, Y., Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Springer, 2006.
  • [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] 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] Friis, J.M., Olesen, S.B.,An Experimental Comparison of Max Flow Algorithms, Aarhus University, Master Thesis, 2014.
  • [11] Gabow, H.N., Scaling Algorithms for Network Problems, Journal of Computer and System Sciences, vol:31(1985), 148–168.
  • [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] Gupta, A., Shortest Paths and Seidel’s Algorithm, CMU, Lecture 4, 2017, 1–10.
  • [14] Medhi, D., Ramasamy, K., Network Routing: Algorithms, Protocols, and Architectures, Morgan Kaufmann Publishers, San Francisco, CA, 2007.
  • [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] Ozturk, A., Yoneylem Arastırması, Ekin Kitabevi, Bursa, Turkey, 2001.
  • [17] Siyah, B., Genetik Algoritma Kullanılarak Noktadan Noktaya Yol ve Rota Planlama, Software Engineer in Deep Learning, WordPress, 2014.
  • [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] 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] 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] Yurtay, N., Ayrık Işlemsel Yapılar, Sakarya U¨ niversitesi Ders Notları, 2008, 14–20.

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

Year 2020, Volume: 8 Issue: 2, 279 - 283, 27.10.2020

Öznur İşçi Güneri Burcu Durmuş

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] Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity, Creative Commons, California, USA, 2006.
  • [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] Chabrier, A., Vehicle Routing Problem with Elementary Shortest Path Based Column Generation, Computers and Operations Research, vol:33 (2006), 2972–2990.
  • [4] Cömert, Z., En Kısa Yol Problemi, Bilişim: Paylas¸ım, 2015, 1–6.
  • [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] Çunkas¸, M., Genetik Algoritmalar ve Uygulamaları, Selcuk Universitesi Ders Notları, 2006.
  • [7] Dinitz, Y., Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Springer, 2006.
  • [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] 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] Friis, J.M., Olesen, S.B.,An Experimental Comparison of Max Flow Algorithms, Aarhus University, Master Thesis, 2014.
  • [11] Gabow, H.N., Scaling Algorithms for Network Problems, Journal of Computer and System Sciences, vol:31(1985), 148–168.
  • [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] Gupta, A., Shortest Paths and Seidel’s Algorithm, CMU, Lecture 4, 2017, 1–10.
  • [14] Medhi, D., Ramasamy, K., Network Routing: Algorithms, Protocols, and Architectures, Morgan Kaufmann Publishers, San Francisco, CA, 2007.
  • [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] Ozturk, A., Yoneylem Arastırması, Ekin Kitabevi, Bursa, Turkey, 2001.
  • [17] Siyah, B., Genetik Algoritma Kullanılarak Noktadan Noktaya Yol ve Rota Planlama, Software Engineer in Deep Learning, WordPress, 2014.
  • [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] 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] 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] Yurtay, N., Ayrık Işlemsel Yapılar, Sakarya U¨ niversitesi Ders Notları, 2008, 14–20.
There are 21 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Articles
Authors

Öznur İşçi Güneri 0000-0003-3677-7121

Burcu Durmuş 0000-0002-0298-0802

Publication Date October 27, 2020
Submission Date July 17, 2019
Acceptance Date October 3, 2020
Published in Issue Year 2020 Volume: 8 Issue: 2

Cite

APA İşçi Güneri, Ö., & Durmuş, B. (2020). Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp Journal of Mathematics, 8(2), 279-283.
AMA İşçi Güneri Ö, Durmuş B. Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp J. Math. October 2020;8(2):279-283.
Chicago İşçi Güneri, Öznur, and Burcu Durmuş. “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”. Konuralp Journal of Mathematics 8, no. 2 (October 2020): 279-83.
EndNote İşçi Güneri Ö, Durmuş B (October 1, 2020) Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp Journal of Mathematics 8 2 279–283.
IEEE Ö. İşçi Güneri and B. Durmuş, “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”, Konuralp J. Math., vol. 8, no. 2, pp. 279–283, 2020.
ISNAD İşçi Güneri, Öznur - Durmuş, Burcu. “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”. Konuralp Journal of Mathematics 8/2 (October 2020), 279-283.
JAMA İşçi Güneri Ö, Durmuş B. Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp J. Math. 2020;8:279–283.
MLA İşçi Güneri, Öznur and Burcu Durmuş. “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”. Konuralp Journal of Mathematics, vol. 8, no. 2, 2020, pp. 279-83.
Vancouver İşçi Güneri Ö, Durmuş B. Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp J. Math. 2020;8(2):279-83.
 Download Cover Image
Creative Commons License
The published articles in KJM are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.