Comparative Analysis of Dijkstra and A* Algorithms for Determining the Shortest Route - Ardiansyah Ardiansyah; Abdul Muin Nasution; Muhammad Iqbal (Komunitas Dosen Indonesia, 2025)
This study presents a comparative analysis of Dijkstra and A* algorithms for determining the shortest route in an urban road network scenario, specifically from SMKN 9 Medan to Gramedia Gajah Mada, Medan. The road network is modeled as a weighted graph, where nodes represent key locations, and edges represent inter-node distances derived from Google Maps. Three alternative routes are evaluated based on inter-node distances and direct heuristic distances to the destination. Dijkstra’s algorithm, an uninformed search method, guarantees optimality by exhaustively exploring all possible paths with non-negative weights. In contrast, the A* algorithm incorporates a heuristic function that estimates the remaining distance to the goal, enhancing search efficiency by focusing on the most promising paths. Both algorithms are applied to the same graph data for a fair comparison, with performance metrics including total route distance, number of nodes explored, and computational efficiency. The results show that while both algorithms identify the same optimal route (A–B–E–G, 5.7 km), A* outperforms Dijkstra in terms of computational efficiency, exploring fewer nodes and requiring less computation time. These findings suggest that while Dijkstra remains reliable for smaller networks, A* is better suited for real-world navigation applications where efficiency and scalability are critical. This study provides empirical evidence supporting the use of heuristic-based algorithms in urban route planning systems.