Comparative Analysis of Dijkstra and A* Algorithms for Determining the Shortest Route from SMKN 9 Medan to Gramedia Gajah Mada
Keywords:
Dijkstra, A*, shortest route, graph, heuristic function.Abstract
Determining the shortest route is an important problem in navigation system development, especially in urban environments with complex road networks. This study aims to compare the performance of the Dijkstra algorithm and the A* algorithm in finding the shortest route from SMKN 9 Medan to Gramedia Gajah Mada. Distance data between nodes and heuristic values were obtained from Google Maps and represented in a graph structure for route computation. Both algorithms were applied to three predetermined route alternatives. The results show that Dijkstra and A* produced the same optimal route, namely A–B–E–G, with a total distance of 5.7 km. However, the A* algorithm demonstrated higher efficiency by exploring fewer nodes and requiring less computational time due to the use of a heuristic function. Therefore, the A* algorithm is more suitable for intelligent navigation systems requiring faster computation, while the Dijkstra algorithm is more appropriate for smaller networks without heuristic considerations.
References
Tamatjita, E. N. dan Mahastama, A. W., “Shortest Path with Dynamic Weight Implementation Using Dijkstra’s Algorithm,” ComTech: Computer, Mathematics and Engineering Applications, vol. 7, no. 3, pp. 161-171, Sept. 2016. [Online]. Available: https://journal.binus.ac.id/index.php/comtech/article/download/2534/3017 .
P. S. Pioh, “Graph model for minimal distance and optimal circulation in urban design,” Jurnal Ilmiah Sains, vol. 12, no. 1, pp. 1–7, Apr. 2012. [Online]. Available: https://media.neliti.com/media/publications/288321-graph-model-for-minimal-distance-and-opt-10da6f0b.pdf
P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968. doi:10.1109/TSSC.1968.300136.
A. C. Prasetyo, M. P. Arnandi, H. S. Hudnanto, and B. Setiaji, “Perbandingan Algoritma A* dan Dijkstra dalam Menentukan Rute Terdekat,” *Jurnal Ilmiah SISFOTENIKA*, vol. 9, no. 1, pp. 36–46, Jan. 2019. [Online]. Available: https://media.neliti.com/media/publications/538345-none-2282d3b8.pdf
J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
Y. Feng, W. Zhang, and J. Zhu, “Application of an Improved A* Algorithm for the Path Analysis of Urban Multi-Type Transportation Systems,” Applied Sciences, vol. 13, no. 24, p. 13090, 2023. doi:10.3390/app132413090. [Online]. Available: https://www.mdpi.com/2076-3417/13/24/13090
A. Madkour, W. G. Aref, F. Ur Rehman, M. A. Rahman, and S. Basalamah, “A Survey of Shortest-Path Algorithms,” arXiv preprint arXiv:1705.02044, May 2017. [Online]. Available: https://arxiv.org/abs/1705.02044
L. Fu, “Heuristic shortest path algorithms for transportation applications,” Computers & Operations Research, vol. 33, no. 4, pp. 1012-1040, 2006. Doi: 10.1016/j.cor.2005.03.027
F. Wang, W. Liu, H. Liu, and H. Zhang, “Estimating O-D Travel Time Matrix by Google Maps API: Implementation, Advantages and Implications,” *Journal of Transport Geography*, vol. 86, p. 102770, 2020. doi:10.1016/j.jtrangeo.2020.102770.
S. Shukla, “Edge Relaxation Property for Dijkstra's Algorithm and Bellman–Ford’s Algorithm,” *GeeksforGeeks*, Nov. 30, 2023. Accessed: Feb. 18, 2025. [Online]. Available: https://www.geeksforgeeks.org/edge-relaxation-property-for-dijkstras-algorithm-and-bellman-fords-algorithm/
X. Guo and X. Luo, “Global Path Search based on A* Algorithm,” in Proc. Int. Conf. Transportation & Logistics, Information & Communication, Smart City (TLICSC), vol. 161, pp. 369–374, Dec. 2018.
T. Hossain et al., “Comprehensive Review of the A* Algorithm: Theory, Implementation and Applications,” 2024. [Online]. Available: https://www.researchgate.net/publication/378521690_Comprehensive-Review-of-the-A-Algorithm-Theory-Implementation-and-Applications.pdf
Programiz, “Online Python Compiler (Interpreter),” Programiz.com. Accessed: Oktober. 29, 2025. [Online]. Available: https://www.programiz.com/python-programming/online-compiler
A. Ardiansyah, “Source code for shortest-path analysis (Dijkstra & A*),” Google Drive, Accessed: Okt. 28, 2025.
[Online]. Available: https://drive.google.com/file/d/1qaHlSOgYVoMRDP5LzCIvWZivLKatGjHl/view
Lubis, H. S. (2009). Perbandingan Algoritma Greedy dan Dijkstra untuk menentukan lintasan terpendek. Skripsi Universitas Sumatera Utara.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Ardiansyah Ardiansyah
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
