Efficiency Evaluation of Shortest Path Algorithms

Abstract—While the ever growing computational capabilities of devices that are used for man-machine interaction are taken for granted, the need to find their most optimum use is as important as ever. This issue is particularly relevant when considering solutions where the determination of the shortest path between given points (nodes) is one of the basic operations. In more complex executions of the shortest paths, sets of paths with the shortest distance between a single initial (source) point and all other destination points, as well as between all pairs of points, are to be found. For each of these approaches, individual algorithms with specific features have been worked out over the past decades. With that in mind, the present article seeks to explore this problem and is structured in such a way as to describe some of the selected algorithms solving the shortest path problem, and to analyse the efficiency of these algorithms during their operation in directed graphs of different type. The study shows that the efficiency varies among algorithms under investigation and allows to suggest which one ought to be used to solve a specific variant of the shortest path problem. Keywords-shortest path; algorithms; efficiency; evaluation I