Application of Modified Kruskal Algorithms in Determining Tourism Routes Optimization in Banda Aceh City

Optimizing tourist route planning has practical implications for both visitor experience and urban sustainability. This study presents a degree-constrained, Kruskal-inspired heuristic for constructing a Hamiltonian path that visits each attraction exactly once while minimizing the total road distance. Ten major attractions in Banda Aceh, Indonesia, were modeled as nodes in a weighted graph using pairwise driving distances from Google Maps (collected 5 October 2019–December 2020). The heuristic generated a continuous route of 21.5 km that spans all attractions, outperforming a minimum spanning tree (MST) baseline of 24.3 km. The method was implemented in a web map and an Android prototype to demonstrate practical usability. While computationally efficient and easy to deploy, the approach does not guarantee global optimality. Limitations include distance-only optimization and a single-city evaluation; future work will integrate time-dependent costs and user preferences to enhance the model's effectiveness.