Analisis Perbandingan Algoritma Nearest Neighbor dan Branch and Bound dalam Penentuan Rute Wisata Pulau Penyengat Berbasis Graf Berbobot - Nurul Hilda Syani Putri; Mirta Fera; Dina Irsandi; Tirta Dwi Arliyanti (Universitas Ma'arif Lampung, 2026)
This study aims to compare the Nearest Neighbour and Branch and Bound algorithms in determining tourism routes on Penyengat Island using weighted graph modeling and to analyze the effect of graph structure on the resulting routes. A quantitative approach based on graph theory was employed in this study. The data were obtained through direct observation in the form of distances between tourist locations, while travel time and number of steps were used as supporting data. Tourist locations were represented as vertices and the connections between locations as weighted edges, with distance used as the main parameter. The graph used in this study was an undirected weighted and incomplete graph with the starting point located at vertex A (Harbor). Route efficiency was evaluated by calculating the total path weight generated by each algorithm. The results showed that the Branch and Bound algorithm produced a more efficient route than the Nearest Neighbour algorithm. In addition, the incomplete graph structure caused repeated vertices in the routes generated by both algorithms. These findings indicate that graph connectivity influences route efficiency in weighted graph-based tourism routing.