Analysis of Dijkstra’s and A* Algorithms for the Shortest Route Problem

Abstract

Finding an efficient route between two locations is a common requirement in modern navigation systems. The Shortest Route Problem (SRP) for travel between JB Sentral and KSL City Mall in Johor Bahru, Malaysia, is compared in this paper between Dijkstra's algorithm and the A* algorithm. Road network data were collected from Google Maps and converted into a weighted graph, where road intersections are modeled as nodes and road segments as edges with distance values. Both algorithms were implemented using Python and evaluated based on the total route distance and the number of iterations required to reach the destination. The A* algorithm completes the search using fewer iterations compared to Dijkstra’s algorithm, showing better efficiency. These findings suggest that while Dijkstra’s algorithm remains accurat, the A* algorithm is more suitable for applications that require faster route computation.