Optimasi Jalur Terpendek Menggunakan Algoritma Dijkstra dan Greedy pada Sistem Informasi Geografis - Taneo, Rizaldy E; Ndun, Riandri; Diana Y.A.; Do'o, Faldi (Jurnal Kridatama Sains dan Teknologi, 2025)
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