Implementasi Algoritma Dijkstra dan Bellman-Ford untuk Optimasi Rute Pemadam Kebakaran di Kota Praya
DOI:
https://doi.org/10.35746/jtim.v7i2.744Keywords:
Dijkstra's Algorithm, Bellman-Ford Algorithm, Shortest Path, Firefighter Route Optimization, Praya CityAbstract
Forest and land fires are critical emergencies requiring rapid response to minimize casualties and property damage. In urban areas like Praya City, fire department response delays are often caused by inefficient routing, especially with traffic congestion and complex road infrastructure. This study aims to analyze and compare the performance of Dijkstra's and Bellman-Ford's algorithms for optimizing firefighter routes in Praya City. This quantitative research utilized a computational and comparative analysis approach. Road network data from Praya City was obtained from Google Maps and modeled as a static graph consisting of 17 nodes and weighted edges repre-senting actual distances. Dijkstra's and Bellman-Ford's algorithms were implemented in Python to find the shortest routes from a designated starting point (Fire Department office) to all other nodes. Performance was evaluated based on route optimality, completeness, and computation time. Both Dijkstra's and Bellman-Ford's algorithms successfully identified identical optimal shortest routes for all tested origin-destination pairs within the Praya City graph. However, Dijkstra's algorithm demonstrated significantly superior computational efficiency, with an average computation time of 0.5 seconds, compared to Bellman-Ford's 1.5 seconds. For optimizing firefighter routes on the static road network graph of Praya City, Dijkstra's algorithm is recommended due to its combi-nation of optimality and superior speed. This finding provides an empirical basis for developing more efficient emergency response navigation systems. Future research should focus on inte-grating dynamic parameters like real-time traffic data.
Downloads
References
N. Challands, “The relationships between fire service response time and fire outcomes,” Fire Technol, vol. 46, no. 3, pp. 665–676, Jul. 2010, https://doi.org/10.1007/s10694-009-0111-y.
J. Monteiro, N. Sousa, J. Coutinho-Rodrigues, and E. Natividade-Jesus, “Challenges Ahead for Sustainable Cities: An Urban Form and Transport System Review,” Jan. 01, 2024, Multidisciplinary Digital Publishing Institute (MDPI). https://doi.org/10.3390/en17020409.
Dataset - Satu Data NTB.” Accessed: May 26, 2025. https://data.ntbprov.go.id/dataset/9cc4c25d-fb17-44fc-be7e-b6932897007a/show
D. S. Septifany, A. L. Nugraha, and M. Awaluddin, "ANALISIS OPTIMALISASI RUTE PEMADAM KEBAKARAN BER-DASARKAN AREA CAKUPAN PIPA HIDRAN DI KOTA SEMARANG," Jurnal Geodesi Undip, vol. 6, no. 3, pp. 28-36, Sep. 2017, https://ejournal3.undip.ac.id/index.php/geodesi/article/view/17183.
B. Junanda, D. Kurniadi and Y. Huda, "PENCARIAN RUTE TERPENDEK MENGGUNAKAN ALGORITMA DIJKSTRA PADA SISTEM INFORMASI GEOGRAFIS PEMETAAN STASIUN PENGISIAN BAHAN BAKAR UMUM," Jurnal Voteteknika, vol. 4, no. 1, pp. 107-115, 2016, http://dx.doi.org/10.24036/voteteknika.v4i1.6014.
L. Y. . Sipayung, C. R. . Sinaga, and A. C. . Sagala, “Application of Dijkstra’s Algorithm to Determine the Shortest Route from City Center to Medan City Tourist Attractions”, CNAHPC, vol. 5, no. 2, pp. 648–655, Aug. 2023, https://doi.org/10.47709/cnahpc.v5i2.2699.
I. Putu, W. Gautama, and K. Hermanto, “Penentuan Rute Terpendek dengan Menggunakan Algoritma Dijkstra pada Jalur Bus Sekolah,” Jurnal Matematika, vol. 10, no. 2, pp. 116–123, Dec. 2020, https://doi.org/10.24843/JMAT.2020.V10.I02.P128.
T. J. Arsita, N. T. Lapatta, Y. Y. Joefri, D. S. Angreni, and S. A. Pratama, “Optimization of Urban Waste Collection Routes Using the Held-Karp Algorithm in a Web and Mobile-Based System”, JAIC, vol. 9, no. 1, pp. 202–210, Jan. 2025, https://doi.org/10.30871/jaic.v9i1.8832.
A. Nabila and R. Aprilia, "Pengoptimalan Jaringan Pipa Primer PUDAM Tirtabina Menggunakan Algoritma Greedy," Jurnal Pendidikan Matematika : Judika Education, vol. 7, no. 2, pp. 187-194, 2024, https://journal.ipm2kpe.or.id/index.php/JUDIKA/article/view/12391.
Y. Darnita and R. Toyib, "Penerapan Algoritma Greedy Dalam Pencarian Jalur Terpendek Pada Instansi-Instasi Penting Di Kota Argamakmur Kabupaten Bengkulu Utara," JURNAL MEDIA INFOTAMA, vol. 15, no. 2, pp. 57-64, 2019, https://doi.org/10.37676/jmi.v15i2.867.
S. Andayani and E. W. Perwitasari, “Penentuan Rute Terpendek Pengambilan Sampah di Kota Merauke Menggunakan Algoritma Dijkstra,” Semantik, vol. 4, no. 1, Nov. 2014, Accessed: May 26, 2025. https://publikasi.dinus.ac.id/index.php/semantik/article/view/859
L. Fitriani and R. N. Labani, "Rancang Bangun Sistem Informasi Geografis Monitoring Data Kebakaran di Dinas Pemadam Kebakaran," Jurnal Algoritma, vol. 16, no. 1, p. 27–33, 2019, https://jurnal.itg.ac.id/index.php/algoritma/article/view/455.
N. Yousefzadeh, R. Sengupta, and S. Ranka, “Dynamic Graph Attention Networks for Travel Time Distribution Prediction in Urban Arterial Roads,” Dec. 2024, https://doi.org/10.48550/arxiv.2412.11095.
M. Apriyaningsih, A. Muid, and N. Nurhasanah, “Prototipe Sistem Pemadam Kebakaran Otomatis Berbasis Mikro-kontroler Atmega328p,” PRISMA FISIKA, vol. 5, no. 3, pp. 106–110, Oct. 2017, https://jurnal.untan.ac.id/index.php/jpfu/article/view/22429.
S. W. G. AbuSalim, R. Ibrahim, M. Z. Saringat, S. Jamel, and J. A. Wahab, “Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization,” vol. 917, no. 1, p. 012077, Sep. 2020, https://doi.org/10.1088/1757-899X/917/1/012077.
H. Yu, D. Zhang, and L. Rauchwerger, “An Adaptive Algorithm Selection Framework,” International Conference on Parallel Architectures and Compilation Techniques, pp. 278–289, Sep. 2004, https://doi.org/10.1109/PACT.2004.1342561.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Sunardi Sunardi, Muhamad Azwar, Dedy Sofian MZ, Angga Radlisa Samsudin, Fazlul Rahman
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
