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

Authors : Öznur İŞÇİ GÜNERİ, Burcu DURMUŞ

Pages : 279-283

View : 12 | Download : 6

Publication Date : 2020-10-27

Article Type : Research Paper

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