Implementasi Algoritma Shortest Path untuk Optimasi Rute pada Sistem Navigasi Lokasi
DOI:
https://doi.org/10.62951/bridge.v4i2.841Keywords:
Algorithm, Dijkstra, Graph, Navigation, Shortest PathAbstract
The increasing complexity of urban road networks demands intelligent navigation systems capable of determining optimal routes efficiently. This research implements the Dijkstra Shortest Path algorithm to optimize route search on a location navigation system in Medan City. The system models a road network as a weighted graph comprising 57 strategic locations and over 90 road connections, represented using adjacency list data structures. The Dijkstra algorithm, implemented in Python using the heapq module for priority queue management, achieves an optimal time complexity of O((V+E) log V). The system features five main functions: shortest route search, popular routes, location listing, dynamic location addition, and dynamic road connection addition. System testing using a case study from Kualanamu Airport to the University of North Sumatra (USU) yielded an optimal route of 16.5 km through 4 road segments. Results demonstrate that the system successfully determines the most efficient route, provides accurate distance and travel time information for multiple transport modes (motorcycle, car, walking), and presents step-by-step journey guidance. This research contributes as a practical reference for applying shortest path algorithms in urban areas and serves as a foundation for developing more complex navigation applications in the future.
Downloads
References
Adam Puspabhuana, Andhika, Yudi Triyana, Muhammad Rifky Adhani, A. S. (2025). Komtekinfo journal, 102-114. https://doi.org/10.35134/komtekinfo.v12i2.645
Alvito, P., & Ikhsan, M. (2025). Visualisasi dan perbandingan efisiensi algoritma A*, Greedy, dan Dijkstra pada data OpenStreetMap Kota Medan. Jurnal Riset Komputer, 12(4), 2407-389. https://doi.org/10.30865/jurikom.v12i4.8869
Amin, A., & Hendrik, B. (2025). Analisis penerapan algoritma Dijkstra dalam optimasi penentuan rute: Sebuah kajian literatur sistematis. Journal of Education Research, 6(1), 100-106. https://doi.org/10.37985/jer.v6i1.2155
Andini, M., Kultsum, R. U., Raihan, M. H. R., & Lestari, S. (2025). 1746-16-4798-1-10-20250208 (1). 9(1), 290-302. https://doi.org/10.52362/jisamar.v9i1.1746
Angul, A., Fallo, D., Tanggo, K. V., Belo, I. N. A., & Hoar, F. (2025). Implementasi algoritma Dijkstra dan Greedy dalam penyelesaian masalah rute terpendek. Jurnal Kridatama Sains Dan Teknologi, 7(01), 489-496. https://doi.org/10.53863/kst.v7i01.1654
Asis, M. A., Mude, M. A., Astiani, R., & Kurnia Prihandani, S. N. (2024). Shortest route navigation indoors using digital maps. Indonesian Journal of Data and Science, 4(3), 169-175. https://doi.org/10.56705/ijodas.v4i3.110
Chandra, R., Arifin Prasetyo, T., Sitorus, R. A. P., Situmorang, P. H., Hutasoit, Y. S. R., & Manik, T. E. (2024). Design and implementation of the shortest path navigation in Samosir District using branch and bound algorithm. Jurnal RESTI, 8(2), 242-249. https://doi.org/10.29207/resti.v8i2.5585
Dima, J., Hamzah, M. S., Tallo, C. G., & Fallo, D. Y. A. (2025). Tinjauan literatur tentang pemanfaatan algoritma Greedy untuk pencarian jalur terpendek. Jurnal Kridatama Sains Dan Teknologi, 7(01), 519-528. https://doi.org/10.53863/kst.v7i01.1683
Grujic, Z., & Grujic, B. (2025). Optimal routing in urban road networks: A graph-based approach using Dijkstra's algorithm. Applied Sciences (Switzerland), 15(8). https://doi.org/10.3390/app15084162
Hadi, H. M., & Ibrahim, I. M. (2025). A comprehensive review of shortest path algorithms for network routing. Asian Journal of Research in Computer Science, 18(3), 152-175. https://doi.org/10.9734/ajrcos/2025/v18i3584
Hevlie, W., Nazry, S., Riza, F., Rizky, F., Gultom, Z. A., Haris, M., … Barus, B. (2025). Model optimasi rute transportasi berbasis pemrograman linear. Jurnal Sistem Informasi Triguna Dharma (JURSI TGD), 4(1), 75-81. https://doi.org/10.53513/jursi.v4i1.10586
Jelita, F., Fallo, D., & Miru, Y. G. (2025). Optimalisasi rute menggunakan algoritma Dijkstra dan Greedy: Sebuah pendekatan komparatif. Jurnal Kridatama Sains Dan Teknologi, 7(01), 555-562. https://doi.org/10.53863/kst.v7i01.1659
Jumali, M. A., Rizki, G., Ulum, M. B., & Prianto, Y. C. (2026). Model optimasi distribusi minimum biaya berbasis transportation problem dan shortest path. Jurnal Teknik Industri Terintegrasi (JUTIN), 9(1 SE-Articles of Research), 328-333. Retrieved from https://journal.universitaspahlawan.ac.id/index.php/jutin/article/view/52517
Kurniawan, M., Farida, & Agustini, S. (2021). Rute terpendek algoritma particle swarm optimization dan brute force untuk optimasi travelling salesman problem. Jurnal Teknik Informatika, 14(2), 191-200. Retrieved from http://journal.uinjkt.ac.id/index.php/ti
M, P. M. P. (2023). Optimasi metode travelling salesman problem (TSP) dalam menyelesaikan kasus rute terpendek pengiriman barang. MEANS (Media Informasi Analisa Dan Sistem), 8(1), 34-39. https://doi.org/10.54367/means.v8i1.2637
Probrini, E. (2025). … with Dijkstra's algorithm shortest route search with Dijkstra's algorithm: Pencarian rute terpendek dengan algoritma Dijkstra shortest route search with Dijkstra's … Jurnal| Eduelektromatika, 6(1), 50-57. Retrieved from https://www.jurnal.sttp.ac.id/index.php/eduelektromatika/article/view/81
Rahmadi, D., Putri, T. N., & Ilmi, D. A. (2025). Optimizing travel routes between Jakarta and Surabaya using the Dijkstra algorithm. Al-Aqlu: Jurnal Matematika, Teknik Dan Sains, 3(2985-4369), 74-81. https://doi.org/10.59896/aqlu.v3i1.140
Taneo, R. E., Ndun, R., Fallo, D. Y. A., & Do'o, F. (2025). Optimasi jalur terpendek menggunakan algoritma Dijkstra dan Greedy pada sistem informasi geografis. Jurnal Kridatama Sains Dan Teknologi, 7(01), 572-852. https://doi.org/10.53863/kst.v7i01.1664
Technology, N., Baidawi, T., Kuswara, H., Wahyudi, E., Bina, U., Informatika, S., … Routing, V. (2025). ALGORITMA GENETIKA BERBASIS GOOGLE MAPS API. 5(2), 57-65.
Wijaya, D. R., Athallah, A., Noor'afina, T. N., Telnoni, P. A., & Budiwati, S. D. (2023). Cargo route optimization using shortest path algorithms: Runtime and validity comparison. Journal of Computer Science, 19(11), 1369-1379. https://doi.org/10.3844/jcssp.2023.1369.1379
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Bridge : Jurnal Publikasi Sistem Informasi dan Telekomunikasi
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
