Araştırma Makalesi
BibTex RIS Kaynak Göster

Yıl 2020, Cilt: 8 Sayı: 2, 279 - 283, 27.10.2020

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

Öz

Kaynakça

  • [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

Yıl 2020, Cilt: 8 Sayı: 2, 279 - 283, 27.10.2020

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

Öz

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.

Anahtar Kelimeler

Optimization shortest path problems Classic algorithm Heuristic algorithms Complexity

Kaynakça

  • [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.
Toplam 21 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Matematik
Bölüm Articles
Yazarlar

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

Burcu Durmuş 0000-0002-0298-0802

Yayımlanma Tarihi 27 Ekim 2020
Gönderilme Tarihi 17 Temmuz 2019
Kabul Tarihi 3 Ekim 2020
Yayımlandığı Sayı Yıl 2020 Cilt: 8 Sayı: 2

Kaynak Göster

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. Ekim 2020;8(2):279-283.
Chicago İşçi Güneri, Öznur, ve Burcu Durmuş. “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”. Konuralp Journal of Mathematics 8, sy. 2 (Ekim 2020): 279-83.
EndNote İşçi Güneri Ö, Durmuş B (01 Ekim 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 ve B. Durmuş, “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”, Konuralp J. Math., c. 8, sy. 2, ss. 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 (Ekim 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 ve Burcu Durmuş. “Classical and Heuristic Algorithms Used in Solving the Shortest Path Problem and Time Complexity”. Konuralp Journal of Mathematics, c. 8, sy. 2, 2020, ss. 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.
 Kapak Resmi İndir
Creative Commons License
The published articles in KJM are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.