Analisis Perbandingan Algoritma Dijkstra dan A-Star dalam Menentukan Rute Terpendek
Kata Kunci:
Dijkstra Algorithm, A-Star Algorithm, Shortest Route, Compute Tim, Heuristics, Python, NetworkX;Abstrak
Some applications, such as Google Maps, require an effective algorithm, to determine the shortest route. The two most commonly used algorithms to solve this problem are the Djikstra and A-Star algorithms. The Djikstra algorithm is famous for its accuracy in finding the shortest route by exploring all possible routes, but it has the disadvantage of long computation times on large graphs. The A-Star algorithm, on the other hand, uses heuristics to guide searches to destinations faster, reduce the number of nodes explored, and speed up computational time. The study analyzed the comparison of the two algorithms using Python in Colab. The focus of the research is the computing time and the smallest route accuracy produced. The results showed that both algorithms had the same ability to find the shortest route, but A-Star was more efficient in computing time. Recommendations are given for the use of each algorithm based on graph size and priority of computing needs. This research is expected to provide insight for application developers in choosing the algorithm that best suits their needs.
Unduhan
Referensi
A. C. Prasetyo, M. Prayoga Arnandi, H. S. Hudnanto, and B. Setiaji, “Perbandingan Algoritma Astar dan Dijkstra Dalam Menentukan Rute Terdekat 36 Jurnal Ilmiah SISFOTENIKAJuly201xIJCCS Perbandingan Algoritma Astar dan Dijkistra Dalam Menentukan Rute Terdekat Astar and Dijkistra Algorithm Comparison for Determining the Shortest Route,” J. Ilm. SISFOTENIKAJ, vol. 9, no. 1, pp. 36–46, 2019.
R. Apriaz Diaz Novandi, “Perbandingan Algoritma Djikstra dan Algoritma Floyd-Warshall Dalam Penentuan Lintasan Terpendek (Single Pair Shortest Path),” Makal. IF2251 Strateg. Algoritm., pp. 1–5, 2023.
D. Pugas, M. Somantri, and K. Satoto, “Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan Pariwisata Kota Sawahlunto,” Transmisi, vol. 13, no. 1, pp. 27–32, 2011, [Online]. Available: http://www.ejournal.undip.ac.id/index.php/transmisi/article/view/3632
I. B. Gede Wahyu Antara Dalem, “Penerapan Algoritma A* (Star) Menggunakan Graph Untuk Menghitung Jarak Terpendek,” J. Resist. (Rekayasa Sist. Komputer), vol. 1, no. 1, pp. 41–47, 2018, doi: 10.31598/jurnalresistor.v1i1.253.
R. Umar, A. Yudhana, and A. Prayudi, “Perbandingan, Analisis Djikstra, Algoritma Warshall, Floyd Pencarian, Dalam Terdekat Pada Objek Wisata Kabupaten Dompu,” J. Teknol. Inf. dan Ilmu Komput., vol. 8, no. 2, pp. 227–234, 2021, doi: 10.25126/jtiik.202182866.
