Penerapan Minimun Spanning Tree dalam Penentuan Rute Objek Wisata di Kota Medan Menggunakan Algoritma Prim - Melissa Chandra; Felicia Eldora; Ledy Meva Tiurma Gultom; Khoiriyati Azmi; Nerli Khairani (Pusat riset dan Inovasi Nasional, 2025)
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.