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

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

doi:10.53863/kst.v7i01.1664

Authors

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

Keywords:

Geographic Information Systems, shortest path, Dijkstra algorithm, Greedy algorithm, route optimization

Abstract

The shortest path search is a primary challenge in the development of Geographic Information Systems (GIS), especially for navigation, logistics, and regional planning applications. This study discusses the optimization of the shortest path by comparing two popular algorithms, Dijkstra and Greedy Best-First Search (Greedy BFS), on a weighted graph representing a road network. The research was conducted experimentally by constructing a fictitious graph consisting of 10 nodes and 15 edges, where each edge has a weight representing the distance between locations. Both algorithms were implemented using the Python programming language and the networkx library. Experimental results show that the Dijkstra algorithm consistently produces the optimal shortest path with the minimum total distance, although it requires longer execution time. In contrast, the Greedy BFS algorithm can find solutions more quickly, but the resulting path is not always optimal, depending on the quality of the heuristic used. In the case study, Dijkstra produced a path with a total distance of 14 km, while Greedy BFS produced a path of 17 km with shorter execution time. The visualization of results clarifies the decision differences at branching nodes between the two algorithms. This study concludes that the choice of algorithm in GIS should be adjusted to the application's needs; Dijkstra is recommended for applications requiring high accuracy, while Greedy BFS is more suitable for applications needing fast response. The results of this research are expected to serve as a reference in the development of GIS based on shortest path optimization

References

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.