Penerapan Minimun Spanning Tree dalam Penentuan Rute Objek Wisata di Kota Medan Menggunakan Algoritma Prim
DOI:
https://doi.org/10.55606/jurrimipa.v4i3.7710Keywords:
Minimum Spanning Tree, Prim’s Algorithm, Route Optimization, Tourist Destinations, Weighted GraphAbstract
The development of science and technology has encouraged the utilization of graph theory in solving optimization problems, particularly in transportation systems and tourism route planning. Medan City, as a metropolitan area with dense road networks and widely dispersed tourist destinations, faces challenges in selecting efficient travel routes. This research aims to determine the optimal route between tourist destinations in Medan City using the Minimum Spanning Tree (MST) method with Prim’s Algorithm. The research was conducted using a weighted graph modeling approach, where each tourist destination is represented as a vertex and the distance between destinations is represented as an edge weight. Distance data and estimated travel time were obtained through digital mapping using Google Maps and then analyzed through iterations of Prim’s Algorithm to produce a minimum spanning tree without forming cycles. The results show that all 23 tourist destinations are successfully connected in a single MST structure with a minimum total distance of 68.97 km and a travel time of approximately 199 minutes or 3 hours and 19 minutes. This model is expected to serve as a reference for tourism planning and support urban transportation efficiency based on mathematical computation.
Downloads
References
Afrianti, E., Effendi, & Des, W. (2021). Menentukan minimum spanning tree menggunakan algoritma modifikasi dari algoritma Prim dan Kruskal dalam perencanaan rute wisata yang efisien. Jurnal Saintika UNPAM: Jurnal Sains dan Matematika Unpam, 3(2), 103–110. https://doi.org/10.32493/jsmu.v3i2.6706
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.
Amalia, N. T., Novianti, F., & Aisyah Yasmin, Y. R. (2024). Minimum spanning tree rute shopping mall di Surabaya menggunakan algoritma Prim. Jurnal Derivat, 11(1), 10–18. https://doi.org/10.31316/jderivat.v11i1.4955
Efendi, R., Susilo, B., & Prasetyo, Y. A. (2021). Perbandingan algoritma Boruvka dan algoritma Sollin pada optimasi kebutuhan kabel fiber optik Universitas Bengkulu. JSAI: Journal Scientific and Applied Informatics, 4(2), 175–181. https://doi.org/10.36085/jsai.v4i2.1623
Heriansyah, A. B. M., Rizwar, R., Rafliansyah, M., Christian, E., & Pranatawijaya, V. H. (2024). Penerapan algoritma Prim dalam menentukan rute prioritas pengiriman paket express. IGNITE: Journal Islamic Global Network for Information Technology and Entrepreneurship, 2(3), 21–33. https://doi.org/10.59841/ignite.v2i3.1550
Ilahy, W. I., Ahmad, M., & Hartono, B. P. (2023). Optimasi jaringan distribusi air di Desa Gombolharjo menggunakan algoritma Prim. Journal of Mathematics Education and Science, 6(2), 177–183. https://doi.org/10.32665/james.v6i2.1896
Jaro, K. S. A., Khopipah, & Napis. (2025). Matematika diskrit teori graf pada LRT dalam mengatasi kemacetan: Studi literatur. Pentagon: Jurnal Matematika dan Ilmu Pengetahuan Alam, 3(3), 60–71.
Lusiani, A., Sartika, E., Habinuddin, E., Binarto, A., Azis, I., & Kata Kunci. (2021). Algoritma Prim dalam penentuan lintasan terpendek dan lintasan tercepat pada pendistribusian logistik Bulog Jawa Barat. 4–5.
Mas’ud, S. (2024). Penentuan rute pendistribusian gas LPG menggunakan algoritma Prim dengan optimalisasi melalui pergantian sisi. Proximal: Jurnal Penelitian Matematika dan Pendidikan Matematika, 7(1), 9–17. https://doi.org/10.30605/proximal.v7i1.3063
Ningsih, N. P. D. U., & Fitriyanto, M. N. (2021). Perbandingan algoritma Prim, Kruskal, Djikstra, dan Floyd-Warshall untuk memecahkan masalah minimum spanning trees: Perancangan pemasangan pipa saluran air bersih. Jurnal Pendidikan Teknologi Informasi, 6(2), 17–24. https://doi.org/10.33084/bitnet.v6i2.2636
Nugroho, H. T., Sisworo, & Satyananda, D. (2023). Implementasi algoritma pohon merentang minimum (MST) pada permainan. 1–12. https://doi.org/10.17977/um067v2i122022p3
Priharsena, G. A. (2020). Penerapan algoritma Prim dalam perancangan rute perjalanan wisata di Bali.
Rahmadi, D., & Herdianti, R. R. (2024). Penerapan minimum spanning tree dalam menentukan rute terpendek pada wisata di Kota Wonogiri. BASIS: Jurnal Ilmiah Matematika, 3(2), 31–39. https://doi.org/10.30872/basis.v3i2.1390
Sholikhatin, S. A., Prasetyo, A. B., & Nurhopipah, A. (2020). Aplikasi berbasis desktop untuk penyelesaian graph dengan algoritma Kruskal dan algoritma Prim. Jurnal Resistor: Rekayasa Sistem Komputer, 3(2), 89–93. https://doi.org/10.31598/jurnalresistor.v3i2.638
Suryati, C. E., Revida, E., & Siregar, E. M. (2025). Analisis kebijakan implementasi BRT (Bus Rapid Transit) Pemerintah Kota Medan dalam mengatasi kemacetan lalu lintas di Kota Medan. Edusaintek: Jurnal Pendidikan, Sains dan Teknologi, 12(1), 243–252.
Yannuansa, N., Leksono, J. W., Mutrofin, A., & Samudra, A. (2020). Keoptimuman jaringan listrik di perumahan Pulo Asri dengan algoritma Prim. 5(1), 38–44. https://doi.org/10.33752/discovery.v5i1.662
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 JURNAL RISET RUMPUN MATEMATIKA DAN ILMU PENGETAHUAN ALAM
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
