Analisis Perbandingan Algoritma Dijkstra dan Floyd-Warshall dalam Menentukan Rute Terpendek Menuju Puskesmas di Kota Medan
DOI:
https://doi.org/10.62712/juktisi.v5i2.1452Keywords:
Dijkstra Algorithm, Floyd-Warshall Algorithm, Shortest Path, Weighted Graph, Public Health Center, Medan CityAbstract
Pemilihan rute terpendek menuju fasilitas kesehatan merupakan salah satu aspek penting dalam meningkatkan efektivitas pelayanan kesehatan, khususnya pada kondisi yang membutuhkan penanganan secara cepat. Kota Medan memiliki jaringan jalan yang cukup kompleks sehingga diperlukan metode yang mampu menentukan rute terpendek secara optimal menuju puskesmas. Penelitian ini bertujuan untuk menganalisis dan membandingkan kinerja algoritma Dijkstra dan Floyd-Warshall dalam menentukan rute terpendek menuju puskesmas di Kota Medan. Data penelitian berupa jaringan jalan yang dimodelkan sebagai graf berbobot, dengan simpul merepresentasikan persimpangan jalan dan lokasi puskesmas, sedangkan sisi (edge) merepresentasikan ruas jalan dengan bobot berupa jarak tempuh. Implementasi kedua algoritma dilakukan menggunakan bahasa pemrograman Python dengan bantuan pustaka NetworkX untuk pemodelan graf dan pengolahan data. Pengujian dilakukan terhadap beberapa skenario titik asal menuju puskesmas dengan membandingkan parameter waktu komputasi, panjang lintasan yang dihasilkan, penggunaan memori, dan kemampuan algoritma dalam menangani jumlah simpul yang berbeda. Hasil penelitian diharapkan dapat memberikan gambaran mengenai karakteristik, kelebihan, dan keterbatasan masing-masing algoritma dalam penyelesaian masalah pencarian rute terpendek pada jaringan jalan. Selain itu, penelitian ini diharapkan menjadi referensi dalam pengembangan sistem informasi geografis dan sistem pendukung keputusan untuk layanan kesehatan berbasis algoritma graf .
Downloads
References
[1] R. A. Lubis, A. D. Putri, T. Ginting, and S. Utara, “PASIEN RAWAT JALAN DI PUSKESMAS SEI MENCIRIM MEDAN TAHUN 2020,” vol. 3, no. 1, 2020, doi: DOI : https://doi.org/10.35451/jkf.v3i1.467.
[2] N. Gloria, B. Ginting, and D. Agustina, “Implementasi Jaminan Kesehatan Daerah untuk Mencapai Universal Health Coverage ( UHC ) dalam Pelayanan Kesehatan Puskesmas di Puskesmas Teladan Kota Medan,” 2023, https://doi.org/10.56211/pubhealth.v2i2.366.
[3] P. G. J. Hutagalung, R. Ginting, and P. Manalu, “Faktor-faktor yang mempengaruhi pemanfaatan Program Pengelolaan Penyakit Kronis ( Prolanis ) pada lansia di Puskesmas Darussalam Medan,” vol. 02, no. 1, pp. 24–31, 2020, doi.org/10.1616/jpms.v2i2.972.
[4] J. L. Sekip, “HUBUNGAN POLA MAKAN DENGAN STATUS GIZI PADA BALITA The data from the Health Profile of Medan in 2016 revealed that there were balita suffered from severe malnutrition at Lingkungan VII , Kelurahan Sidorejo , Medan Tembung Sub-district . The research used ,” vol. 2, no. 2, 2020, https://doi.org/10.35451/jkk.v2i2.229.
[5] O. M. Çelik and M. Köseoğlu, “A Modified Dijkstra Algorithm for ROS Based Autonomous Mobile Robots,” vol. 1119957, 2023, doi.org/10.28979/jarnas.1119957.
[6] Y. D. Rosita et al., “ScienceDirect ScienceDirect ScienceDirect Implementation of Dijkstra Algorithm and Multi-Criteria Decision- Implementation of Dijkstra Algorithm and Multi-Criteria Decision- Making for Optimal Route Distribution Making for Optimal Route Distribution,” Procedia Comput. Sci., vol. 161, pp. 378–385, 2019, doi: https://doi.org/10.1016/j.procs.2019.11.136.
[7] S. P. Issue, X. Z. Wang, D. Rachmawati, L. Gustin, R. Rahim, and D. Abdullah, “Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization,” 2020, doi: https://doi.org/10.1088/1757-899X/917/1/012077.
[8] Y. Chen, S. Shen, T. Chen, and R. Yang, “Path Optimization Study for Vehicles Evacuation Based on Dijkstra algorithm,” Procedia Eng., vol. 71, pp. 159–165, 2014, doi: https://doi.org/10.1016/j.proeng.2014.04.023.
[9] W. Bielecki and K. Kraska, “Using basis dependence distance vectors in the modified Floyd – Warshall algorithm,” J. Comb. Optim., pp. 253–275, 2015, doi: 10.1007/s10878-014-9740-2.
[10] F. Marpaung, “Road network analysis in Medan city using Floyd-Warshall algorithm for route optimization based on GPS,” vol. 0, pp. 0–7, 2023, doi: https://doi.org/10.2478/9788367405195-047.
[11] O. Butenko and A. Topchiy, “Determination of factors of maximum influence on the occurrence of fires in conditions of limited a priori information in the war zone in the east of Ukraine Визначення факторів максимального впливу на виникнення пожеж в умовах обмеження апріорної інформа,” vol. 24, pp. 166–172, 2023, doi: https://doi.org/10.53452/gb2411.
[12] M. R. Yusuf, N. Nurwan, D. Wungguli, and L. Yahya, “Implementation of the Floyd-Warshall Algorithm and Bellman-Ford Algorithm to Determine the Shortest Path in the Distribution of LPG Gas,” vol. 03004, 2023, doi: https://doi.org/10.1051/e3sconf/202340003004.
[13] R. Ramadani and Z. Busrah, “Perbandingan Algoritma Dijkstra dan Floyd Warshall untuk Penentuan Jalur Terpendek Tim Respons Kebakaran di Kawasan Perdagangan Kota Parepare,” vol. 11, no. 1, pp. 106–120, 2026, doi: https://doi.org/10.26877/jipmat.v11i1.3681.
[14] D. Zugan and R. Požar, “Floyd – Warshall Algorithm for Sparse Graphs,” pp. 1–13, 2025, doi: https://doi.org/10.3390/a18120766.
[15] V. Sakharov, S. Chernyi, S. Saburov, and A. Chertkov, “ScienceDirect ScienceDirect Automatization Search for the Shortest Routes in the Transport Automatization Search the Shortest Routes in the Transport Network Using for the Algorithm Network Using the Floyd-warshell Algorithm TransSiberia 2020 Conference,” Transp. Res. Procedia, vol. 54, no. 2020, pp. 1–11, 2021, doi: https://doi.org/10.1016/j.trpro.2021.02.041.
[16] M. Nizar et al., “ScienceDirect Procedia ScienceDirect On using using Floyd-Warshall Floyd-Warshall under under uncertainty uncertainty for for Influence Influence On Maximization in in Instagram Instagram social social network : network : A A case case study study of of Maximization Indonesian FnB FnB unicorn unicorn company company Indonesian,” Procedia Comput. Sci., vol. 234, pp. 164–171, 2024, doi: https://doi.org/10.1016/j.procs.2024.02.163.
[17] A. V Muholzoev and V. B. Masyagin, “Probabilistic Calculation of Tolerances of the Dimension Chain Based on the Floyd-Warshall Algorithm,” Procedia Eng., vol. 150, pp. 959–962, 2016, doi: https://doi.org/10.1016/j.proeng.2016.07.070.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Khaidir Hanafi, Ilka Zufria
This work is licensed under a Creative Commons Attribution 4.0 International License.
