Analysis and Comparison of Shortest Path Algorithms in Navigation Systems
Gazmend Xhaferi *
Department of Informatics, Faculty of Natural Sciences and Mathematics, University of Tetova, Tetovo, Republic of North Macedonia.
Shkurte Luma-Osmani *
Department of Informatics, Faculty of Natural Sciences and Mathematics, University of Tetova, Tetovo, Republic of North Macedonia.
Merita Kasa-Halili *
Department of Informatics, Faculty of Natural Sciences and Mathematics, University of Tetova, Tetovo, Republic of North Macedonia.
*Author to whom correspondence should be addressed.
Abstract
The shortest path problem is a fundamental component in the development of modern navigation systems and network optimization applications. This study presents a theoretical and empirical analysis of four widely used shortest path algorithms: A*, Greedy Best-First Search, Dijkstra, and Bellman–Ford. The evaluation is conducted on a graph model derived from the road network of North Macedonia, where cities are represented as vertices and roads as weighted edges based on distance.
The research aims to analyze and compare the effectiveness of these four algorithms when applied to navigation systems for finding the shortest route on a map. The analysis compares the algorithms in terms of solution optimality, execution time, number of explored nodes, and practical computational efficiency. The algorithms were implemented in C++ and evaluated under varying graph sizes and search requirements.
The results indicate that Dijkstra’s and Bellman–Ford algorithms guarantee optimal solutions, although Bellman–Ford incurs significantly higher computational costs. The A* algorithm demonstrates superior practical performance due to the use of an admissible heuristic, substantially reducing the search space without compromising optimality. In contrast, Greedy Best-First Search achieves faster execution in certain scenarios but does not guarantee optimal solutions.
The study concludes that A* provides the most balanced trade-off between efficiency and accuracy for road navigation systems. These findings contribute to a better understanding of shortest-path algorithm performance in real-world transportation network environments.
Keywords: Graph algorithms, A*, Dijkstra, greedy best-first search, bellman-ford, navigation system