Penerapan Algoritma Dijkstra dalam Optimasi Rute Terpendek dari Stasiun Kereta Api Medan ke Universitas Negeri Medan
DOI:
https://doi.org/10.62383/polygon.v4i3.961Keywords:
Dijkstra's Algorithm, Graph Theory, Route Optimization, Shortest Path, Urban TransportationAbstract
The increasing complexity of urban transportation systems demands intelligent and measurable navigation methods. Medan City, the capital of North Sumatra Province, has a dense road network with multiple route options that often confuse road users. Dijkstra's Algorithm, developed by Edsger Wybe Dijkstra in 1959, is a greedy-based computational approach proven effective for solving the shortest path problem on non-negative weighted graphs. This study applies Dijkstra's Algorithm to determine the shortest route from Medan Railway Station to Universitas Negeri Medan (UNIMED). The road network was modeled as an undirected weighted graph with 15 nodes and 16 edges, where edge weights represent actual road distances measured via Google Maps. The graph has a density of 0.152, confirming its sparse graph characteristic. Three alternative routes were identified and analyzed. The algorithm was implemented in Python 3 using the heapq module as a priority queue. Results show that the optimal route is A → B → C → E → F → M → N → O via Jl. M.T. Haryono, Jl. Aipda KS Tubun, Jl. Madong Lubis, and Jl. Prof. H.M. Yamin, with a total distance of 6.64 km. This achieves 99.1% accuracy compared to Google Maps, with a deviation of only 0.06 km. The optimal route is 6.25% more efficient than Alternative Route 1 (7.30 km) and 11.9% more efficient than Alternative Route 2 (7.54 km). The algorithm executes in under 1 millisecond with time complexity O((V+E) log V). These findings confirm Dijkstra's Algorithm as highly effective for medium-scale urban road network optimization.
Downloads
References
Abdurrahman, Saragih, A. N. A., Kartika, D., Kanaya, N. S., & Nasution, T. A. A. (2025). Implementasi algoritma Dijkstra untuk menentukan rute terpendek dari Universitas Negeri Medan menuju Thamrin Plaza Medan. Jurnal Ilmiah Matematika, 13(2), 198–199. https://doi.org/10.26740/mathunesa.v13n1.p147-156
Alfatah, D. (2025). Implementation of a genetic algorithm to determine the minimum spanning tree (MST) in an undirected graph. Jurnal Komputer Indonesia, 4(1), 41–54. https://doi.org/10.37676/jki.v4i1.907
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
Arimbawa, I. B. K. P., & Permana, P. N. A. (2025). Penerapan algoritma Dijkstra pada pencarian rute terpendek ke Puskesmas Denpasar Utara II. Digital Transformation Technology, 5(2), 92–97. https://doi.org/10.47709/digitech.v5i2.7043
Estiningdyah, M. M. S. U. (2025). Inovasi pendidikan nusantara. Inovasi Pendidikan Nusantara, 6(2), 188–196.
Jelita, F., Fallo, D., & Miru, Y. G. (2025). Optimalisasi rute menggunakan algoritma Dijkstra dan greedy: Sebuah pendekatan komparatif. Jurnal Kridatama Sains dan Teknologi, 7(1), 555–562. https://doi.org/10.53863/kst.v7i01.1659
Kuncoro, F., Zulkarnain, I. A., & Buntoro, G. A. (2024). Menentukan rute terpendek pada TPAMrican. Jurnal Ilmiah Teknik Informatika, 18(2), 200–211. https://doi.org/10.35457/antivirus.v18i2.3785
Musridho, R. J., Rusnedy, H., & Sudirman, W. F. R. (2025). Analisis komparatif algoritma Dijkstra dan Google Maps API dalam penentuan rute tercepat. RIGGS: Journal of Artificial Intelligence and Digital Business, 4(3), 5017–5022. https://doi.org/10.31004/riggs.v4i3.2264
Purba, J., Manurung, S., Girsang, J., Gulo, J. A., & Sipayung, S. P. (2025). Implementasi algoritma Dijkstra untuk menentukan rute terpendek dari SMA 17 Medan ke Unika St. Thomas. Jurnal Minfo Polgan, 14(1), 1045–1052. https://doi.org/10.33395/jmp.v14i1.14963
Rudy, F., Rajagukguk, S., Harahap, H. H., Arifin, I. W., Hutajulu, R., & Juanda, A. (2025). Digital business progress. Digital Business Progress, 4(1), 1–14. https://doi.org/10.70021/dbp.v4i2.249
Safetra, M. F. C., Desviona, N., Rianti, A., & Prayogi, M. R. (2026). Penerapan teori graf dalam kehidupan sehari-hari. https://doi.org/10.62383/algoritma.v4i1.923
Siregar, D., Silalahi, E. K., Panjaitan, C. K., & Harliana, P. (2024). Perbandingan efisiensi algoritma Dijkstra dan algoritma A* (A star) dalam menemukan rute optimal antara Sun Plaza dan Podomoro menggunakan Python. JATI (Jurnal Mahasiswa Teknik Informatika), 9(1), 217–223. https://doi.org/10.36040/jati.v9i1.12269
Taklal, A. J., Teva, A., Nau, T., Tapatab, A. B., Baria, A. V., Hipir, A. L., Liu, H. A., Lubalu, M. T., Fernando, P., Monika, P. M., Kusuma, T., Seran, W. Y., & Lie, W. I. (2024). Implementasi algoritma Dijkstra untuk pencarian rute efisien dalam pengiriman barang di Kota Kupang. JPATI, 1(2), 98–104.
Tampubolon, A. J., Ricardo, E., Simbolon, D. S., Pasaribu, A., Panggabean, J., & Sipayung, S. P. (2025). Implementasi algoritma Dijkstra menentukan rute terpendek dari Unika St. Thomas menuju Kantor Dinas Kependudukan Kota Medan. Jurnal Minfo Polgan, 14(1), 1274–1286. https://doi.org/10.33395/jmp.v14i1.14997
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(1), 572–582. https://doi.org/10.53863/kst.v7i01.1664
Wibowo, A. P., Azmi, K., Azzahra, Y., & Purba, Y. Y. (2025). Penerapan algoritma Dijkstra untuk menentukan rute terpendek dari RS Bina Kasih menuju RS Adam Malik. Jurnal Ilmiah Matematika, 13(1), 157–167. https://doi.org/10.26740/mathunesa.v13n1.p157-167
Wulandari, S., Susilowati, N. R., & Adnyani, L. P. (2022). Sistem transportasi untuk mendukung mobilitas masyarakat. JPSTTD, 1–11. https://doi.org/10.55511/jpsttd.vxxix.xx
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Polygon : Jurnal Ilmu Komputer dan Ilmu Pengetahuan Alam
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
