A study on performance evaluation of optimization algorithms in the shortest path problem

Finding the shortest or least costly path between two points in the shortest time is crucial in many areas. The shortest path problem aims to move from a starting node on a graph to the destination node via the shortest path. Nowadays it is widely used in traffic applications, routing of internet traffic and programming of games. As time went by and with the development of science and technology, many scientists made researches to solve the shortest path problem, and many algorithms were developed. These algorithms address different kinds of problems and the shortest paths between nodes can be found with them. It can be observed that in the literature there are many and different studies on the shortest path problem. The aim of this study is to analyze and compare four of the algorithms used in shortest path problem. Dijkstra, Bellman – Ford, Johnson's and Floyd-Warshall Algorithms are displayed on the graph drawing application. It is discussed that which algorithm is better and more effective in finding the shortest path. The comparison of four different algorithms for positive weighted, non-directional and fully connected graphs on the same graph drawing application is remarkable because there is no study on this subject with the same spesifications. According to the results of the study, it is understood that algorithm that will be used should be selected in line with type of graph and problem. It is proved that Dijkstra algorithm is absolutely must be used for fully connected, positive weighted and non-directional graphs. Keywords: Graph, the shortest path, optimization, Dijkstra, Floyd-Warshall, Bellman-Ford, Johnson's