Research Article
PDF Mendeley EndNote BibTex Cite

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

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

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.

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.

Details

Primary Language English
Subjects Mathematics
Journal Section Articles
Authors

Öznur İŞÇİ GÜNERİ
MUĞLA SITKI KOÇMAN ÜNİVERSİTESİ, FEN FAKÜLTESİ, İSTATİSTİK BÖLÜMÜ
0000-0003-3677-7121
Türkiye


Burcu DURMUŞ (Primary Author)
MUĞLA SITKI KOÇMAN ÜNİVERSİTESİ, FEN FAKÜLTESİ, İSTATİSTİK BÖLÜMÜ
0000-0002-0298-0802
Türkiye

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

Cite

Bibtex @research article { konuralpjournalmath592852, journal = {Konuralp Journal of Mathematics}, eissn = {2147-625X}, address = {}, publisher = {Mehmet Zeki SARIKAYA}, year = {2020}, volume = {8}, number = {2}, pages = {279 - 283}, title = {Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity}, key = {cite}, author = {İşçi Güneri, Öznur and Durmuş, Burcu} }
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 . Retrieved from https://dergipark.org.tr/en/pub/konuralpjournalmath/issue/31495/592852
MLA İşçi Güneri, Ö. , Durmuş, B. "Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity" . Konuralp Journal of Mathematics 8 (2020 ): 279-283 <https://dergipark.org.tr/en/pub/konuralpjournalmath/issue/31495/592852>
Chicago İşçi Güneri, Ö. , Durmuş, B. "Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity". Konuralp Journal of Mathematics 8 (2020 ): 279-283
RIS TY - JOUR T1 - Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity AU - Öznur İşçi Güneri , Burcu Durmuş Y1 - 2020 PY - 2020 N1 - DO - T2 - Konuralp Journal of Mathematics JF - Journal JO - JOR SP - 279 EP - 283 VL - 8 IS - 2 SN - -2147-625X M3 - UR - Y2 - 2020 ER -
EndNote %0 Konuralp Journal of Mathematics Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity %A Öznur İşçi Güneri , Burcu Durmuş %T Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity %D 2020 %J Konuralp Journal of Mathematics %P -2147-625X %V 8 %N 2 %R %U
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 .
AMA İşç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-283.
Vancouver İşçi Güneri Ö. , Durmuş B. Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity. Konuralp Journal of Mathematics. 2020; 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 Journal of Mathematics, vol. 8, no. 2, pp. 279-283, Oct. 2020
Creative Commons License
The published articles in KJM are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.