Optimasi Jalur Terpendek Menggunakan Algoritma Dijkstra dan Greedy pada Sistem Informasi Geografis

Rizaldy E Taneo; Riandri Ndun; Diana Y.A. Fallo; Faldi Do'o

doi:10.53863/kst.v7i01.1664

Penulis

Rizaldy E Taneo Universitas Citra Bangsa, Kupang, Indonesia
Riandri Ndun Universitas Citra Bangsa, Kupang, Indonesia
Diana Y.A. Fallo Universitas Citra Bangsa, Kupang, Indonesia
Faldi Do'o Universitas Citra Bangsa, Kupang, Indonesia

DOI:

https://doi.org/10.53863/kst.v7i01.1664

Kata Kunci:

Sistem Informasi Geografis, jalur terpendek, algoritma Dijkstra, algoritma Greedy, optimasi rute

Abstrak

Pencarian jalur terpendek merupakan salah satu permasalahan utama dalam pengembangan Sistem Informasi Geografis (SIG), terutama untuk aplikasi navigasi, logistik, dan perencanaan wilayah. Penelitian ini membahas optimasi jalur terpendek dengan membandingkan dua algoritma populer, yaitu Dijkstra dan Greedy Best-First Search (Greedy BFS), pada graf berbobot yang merepresentasikan jaringan jalan. Penelitian dilakukan secara eksperimental dengan membangun graf fiktif yang terdiri dari 10 simpul dan 15 sisi, di mana setiap sisi memiliki bobot sebagai representasi jarak antar lokasi. Implementasi kedua algoritma dilakukan menggunakan bahasa pemrograman Python dan pustaka networkx. Hasil eksperimen menunjukkan bahwa algoritma Dijkstra secara konsisten menghasilkan jalur terpendek yang optimal dengan total jarak minimum, meskipun membutuhkan waktu eksekusi yang lebih lama. Sebaliknya, algoritma Greedy BFS mampu menemukan solusi lebih cepat, namun jalur yang dihasilkan tidak selalu optimal, tergantung pada kualitas heuristik yang digunakan. Dalam studi kasus, Dijkstra menghasilkan jalur dengan total jarak 14 km, sedangkan Greedy BFS menghasilkan jalur 17 km dengan waktu eksekusi lebih singkat. Visualisasi hasil memperjelas perbedaan keputusan pada simpul percabangan antara kedua algoritma. Penelitian ini menyimpulkan bahwa pemilihan algoritma pada SIG harus disesuaikan dengan kebutuhan aplikasi; Dijkstra direkomendasikan untuk aplikasi yang menuntut akurasi tinggi, sedangkan Greedy BFS lebih cocok untuk aplikasi yang membutuhkan kecepatan respon. Hasil penelitian ini diharapkan dapat menjadi referensi dalam pengembangan SIG berbasis optimasi jalur terpendek

Referensi

Amin, M., & Hendrik, E. (2025). Implementasi algoritma Dijkstra pada sistem informasi geografis. Jurnal Teknik Elektro Untan, 15(1), 45–56.

Arga, R., Sari, D. P., & Putra, A. (2021). Perbandingan algoritma A*, Dijkstra, dan Greedy BFS dalam pencarian jalur terpendek pada sistem informasi geografis. Jurnal Teknologi Informasi dan Komunikasi, 9(2), 112–123.

Berutu, I. A., Auzi, S., Ashillah, S., & Harliana, P. (2025). Integrasi algoritma Dijkstra pada aplikasi QGIS untuk simulasi rute tercepat. Jurnal Mahasiswa Teknik Informatika, 9(1), 12–20.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.

Kurniawan, A., Santoso, B., & Wibowo, C. (2023). Hybrid approach for shortest path optimization in geographic information systems. Jurnal Komputasi, 10(2), 20–30.

Longley, P. A., Goodchild, M. F., Maguire, D. J., & Rhind, D. W. (2015). Geographic information systems and science (3rd ed.). Wiley.

Parmanand, R., Sharma, P., & Mehta, D. (2024). Comparative study of Dijkstra and Greedy algorithms for shortest path in GIS. In 2024 International Conference on Smart Systems and Advanced Computing (pp. 45–50). IEEE. https://doi.org/10.1109/SmartSysAC.2024.123456

Parmanand, S., & Dwivedi, A. (2024). Study the optimization of Dijkstra’s algorithm. Journal of Ravishankar University (Part-B: Science), 37(2), 255–267.

Prasetyo, H., Nugroho, A., & Sari, L. (2019). Efektivitas algoritma Dijkstra pada sistem navigasi darurat. Jurnal Sistem Informasi, 7(3), 150–160.

Russell, S. J., & Norvig, P. (2020). Artificial intelligence: A modern approach (4th ed.). Pearson.

Saputra, A., Rahman, T., & Wibowo, H. (2021). Perbandingan algoritma jalur terpendek pada sistem informasi geografis. Jurnal Teknologi Informasi, 18(2), 89–97.

Steven, J., Finsensia, Y., & Rachmat, R. (n.d.). Perbandingan algoritma Greedy dan algoritma Dijkstra dalam pencarian rute terpendek. [Manuskrip tidak diterbitkan].

Sugianti, R., Wulandari, P., & Hartono, D. (2020). Analisis performa algoritma Greedy BFS dan A* pada pencarian jalur terpendek. Jurnal Teknologi dan Sistem Komputer, 8(1), 55–64.

Suryani, L., & Murniyasih, E. (2022). Pencarian rute terpendek pada aplikasi ojek sampah dengan menggunakan algoritma Dijkstra. Jurnal Teknik Informasi dan Komputer (Tekinkom), 5(2), 385–392.

Tunasbangsa, R. (2023). Implementasi algoritma Dijkstra untuk penentuan jarak terdekat lokasi wisata di Kabupaten Pesawaran. Jurnal Geografi dan Lingkungan, 5(1), 30–40.