Penerapan Algoritma Bellman-Ford Untuk Optimisasi Pengendara Dalam Menentukan Rute Terpendek UMKM Di Kabupaten Padang Lawas - Putri Indah Julia Hasibuan; Ali Ikhwan (Forum Kerjasama Pendidikan Tinggi (FKPT), 2025)
This study designs a web-based Geographic Information System (GIS) using the Bellman-Ford algorithm to determine the shortest route for Micro, Small, and Medium Enterprises (MSMEs) in Padang Lawas Regency. The main problem faced by MSMEs is the limited and insufficient use of information technology. This condition makes it difficult for the public to find strategic MSME locations and the fastest routes to business sites, leading to low competitiveness and marketing inefficiency. To address this issue, the system was developed using the waterfall model and integrated with Leaflet JS technology, enabling broad accessibility through the web without additional installation. The Bellman-Ford algorithm was chosen for its ability to calculate the shortest path even when negative weights are present in the graph. Test results show that the optimal route obtained is 1.795 km, more efficient compared to an alternative route of 2.563 km, providing a distance saving of about 30%. The system has proven capable of delivering fast and accurate route recommendations while simultaneously presenting MSME location information interactively. The novelty of this research lies in the integration of Bellman-Ford with interactive web-based digital maps specifically for MSME promotion, which has rarely been applied in regional contexts. The purpose of this study is to improve marketing efficiency, expand accessibility, and strengthen the competitiveness of MSMEs in Padang Lawas. Furthermore, this research is expected to make a real contribution to the community in finding MSMEs more quickly and accurately..