THE PROBLEM OF FINDING THE SHORTEST PATH: A COMPARATIVE ANALYSIS OF THE MAIN ALGORITHMS

Abstract

Mathematical models of connections between certain elements are built with the help of graphs. For example, transport, information, computer and other networks, maps of road, railway, air routes, labyrinths, etc. can be depicted in the form of a graph. The question of the shortest path is still one of the most relevant topics in the field of research. Finding the shortest paths in a graph is used in various fields of activity, for example, to find the optimal route between two objects on a terrain map, in freight logistics, in information packet switching systems on the Internet, etc. This article presents the basic principles of three algorithms for finding the shortest path and compares them by analyzing time and space complexity. In addition, the scope of application of various algorithms is summarized. Dijkstra’s algorithm is a classic algorithm for obtaining the shortest path from a particular vertex to any other. It is widely used in road networks. This algorithm can be used only when the graph does not have any edge with negative weight. The Bellman-Ford algorithm can be used on graphs with negative edge weights, as long as the graph does not contain a negative cycle accessible from the source vertex. The result of this algorithm can be used to determine the existence of a negative weight cycle in a graph. The Floyd-Warshall algorithm is a dynamic programming algorithm that can solve the shortest path problem between any two vertices. The method is used on weighted graphs, which can have both positive and negative edge weights, but must not contain negative cycles. Thus, this method is more general in comparison with Dijkstra’s algorithm. However, in practical application, these three algorithms are not directly used, but their modification and optimization are carried out to improve efficiency.