Implementation of the A Star Heuristic Search Algorithm  in Determining the Shortest Path

Leni Marlina; Aswandi; Dedi Gunawan

doi:10.61306/ijecom.v2i1.20

Authors

Leni Marlina Universitas Pembangunan Panca Budi
Aswandi Politeknik Negeri Lhokseumawe
Dedi Gunawan Sekolah Tinggi Ilmu Komputer Cipta Karya Informatika

DOI:

https://doi.org/10.61306/ijecom.v2i1.20

Keywords:

Shortest path, A star heuristic search algorithm, Two-way weighted graph, Heuristic method, Search efficiency

Abstract

Finding the shortest path in a graph can be applied to various fields of shortest distance costs in routes, computer games, robotics or navigation. This study implements the A star heuristic search algorithm in determining the shortest path using the Visual Basic programming language and MySQL database. A star heuristic algorithm is implemented to find the shortest path between two vertices in a two-way weighted graph. We use a heuristic method to estimate the remaining cost from the start node to the destination point. This condition gives the A star algorithm the opportunity to choose the next closest node and optimize the search for the shortest route. Various experiments have been carried out with various graph conditions and with different complicated graphs to test the A star algorithm. The experimental results show that this algorithm succeeds in finding the shortest path efficiently in various situations. Our findings confirm that the A star algorithm has great potential in solving the shortest path search problem with an advantage in combining various information and remaining cost estimates, thereby minimizing the number of explored nodes and producing the shortest path efficiently.

References

R. Astri, “Implementation of A-star algorithm for searching routes near the tsunami evacuation shelter point,” J. RESTI (Rekayasa Sist. Dan Teknol. Informasi), vol. 4, no. 2, pp. 254–259, 2020. DOI: https://doi.org/10.29207/resti.v4i2.1602

H. Hermawan and H. Setiyani, “Implementasi Algoritma A-Star Pada Permainan Komputer Roguelike Berbasis Unity,” J. Algoritm. Log. dan Komputasi, vol. 2, no. 1, 2019. DOI: https://doi.org/10.30813/j-alu.v2i1.1571

G. Mutaqin, J. N. Fadilah, and F. Nugroho, “Implementasi Metode Path Finding dengan Penerapan Algoritma A-Star untuk Mencari Jalur Terpendek pada Game ‘Jumrah Launch Story,’” Walisongo J. Inf. Technol., vol. 3, no. 1, pp. 43–48, 2021. DOI: https://doi.org/10.21580/wjit.2021.3.1.7042

S. Wahyuni and M. Marbun, “Implementation of Data Mining In Predicting the Study Period of Student Using the Naïve Bayes Algorithm Implementation of Data Mining In Predicting the Study Period of Student Using the Naïve Bayes Algorithm,” in IOP Confrence Series: materials Science and engineering, 2020, pp. 4–11. DOI: https://doi.org/10.1088/1757-899X/769/1/012039

S. Wahyuni, kana S. Saragih, and M. I. Perangin-angin, “Implemntasi Metode Decision Tree C4.5 Untuk Menganalisa Mahasiswa Dop Out,” ethos, vol. 6, no. 1, pp. 42–51, 2018.

Husain, M. Zarlis, Z. Nasution, H. T. Sihotang, and S. Wahyuni, “Filsafat Ilmu Komputer Dan Cloud Computing Secara Etimologis,” J. Mantik Penusa, vol. 2, no. 2, pp. 15–21, 2018.

S. Wahyuni, A. Lubis, S. Batubara, and I. K. Siregar, “Implementasi algoritma crc 32 dalam mengidentifikasi Keaslian file,” in Seminar Nasional Royal (SENAR), 2018, vol. 1, no. 1, pp. 1–6.

S. Wahyuni, D. J. Sari, H. Hernawaty, and N. Afifah, “Implementation of the Ternakloka Application membership method in increasing livestock sales in Kota Pari Village,” in International Conference on Sciences Development and Technology, 2022, vol. 2, no. 1, pp. 197–202.

M. M. Attoyibi, F. E. Fikrisa, and A. N. Handayani, “The Implementation of A Star Algorithm (A*) In the Game Education About Numbers Introduction,” in 2nd International Conference on Vocational Education and Training (ICOVET 2018), 2019, pp. 234–238. DOI: https://doi.org/10.2991/icovet-18.2019.57

K. Andesa, H. Herwin, and T. Nasution, “Go-Gallon App With A Star (A*) Algorithm Implementation Using Android Kotlin,” J. Teknol. dan Open Source, vol. 5, no. 1, pp. 24–34, 2022. DOI: https://doi.org/10.36378/jtos.v5i1.2066

I. F. Ashari, “Analysis and Implementation of Augmented Reality Using Markerless and A-Star Algorithm (Case Study: Gedung Kuliah Umum ITERA),” Comput. Eng. Appl. J., vol. 11, no. 3, pp. 177–190, 2022. DOI: https://doi.org/10.18495/comengapp.v11i3.414

S. Wahyuni, D. J. Sari, H. Hernawaty, and N. Afifah, “TERNAKLOKA: A WEB-BASED MARKETPLACE FOR QURBAN AND AQIQAH,” JURTEKSI (Jurnal Teknol. dan Sist. Informasi), vol. 9, no. 2, pp. 249–254, 2023. DOI: https://doi.org/10.33330/jurteksi.v9i2.1662

S. Wahyuni and F. Wadly, “Application Of Inventory And Service Transactions On Web-Based Cv Medan Teknik using the Agile Kanban Method,” Int. J. Comput. Sci. Math. Eng., vol. 2, no. 1, 2023. DOI: https://doi.org/10.61306/ijecom.v2i1.16

I. Taufik, F. M. Kaffah, O. R. Julianda, A. Wahana, and P. Popon, “A-star algorithm implementation for determining the nearest police personnel with the occurrence of the case,” in AIP Conference Proceedings, 2023, vol. 2646, no. 1. DOI: https://doi.org/10.1063/5.0112728

S. Wahyuni, O. S. Sitompul, E. B. Nababan, and P. Sihombing, “Social Network Analysis Text Mining on Networks Publication Citation,” in 2021 International Conference on Data Science, Artificial Intelligence, and Business Analytics (DATABIA), 2021, pp. 35–39. DOI: https://doi.org/10.1109/DATABIA53375.2021.9650327

A. Khaliq and S. N. Sari, “PEMANFAATAN KERANGKA KERJA INVESTIGASI FORENSIK JARINGAN UNTUK IDENTIFIKASI SERANGAN JARINGAN MENGGUNAKAN SISTEM DETEKSI INTRUSI (IDS),” J. Nas. Teknol. Komput., vol. 2, no. 3, pp. 150–158, 2022. DOI: https://doi.org/10.61306/jnastek.v2i3.52

C. Rizal, S. R. Siregar, S. Supiyandi, S. Armasari, and A. Karim, “Penerapan Metode Weighted Product (WP) Dalam Keputusan Rekomendasi Pemilihan Manager Penjualan,” Build. Informatics, Technol. Sci., vol. 3, no. 3, pp. 312–316, 2021. DOI: https://doi.org/10.47065/bits.v3i3.1094

Dwi Ningsih, “Partisipasi Anggota Pemberdayaan Kesejahteraan Keluarga (PKK) Dalam Pengelolaan Sampah Di Dusun Kabunan, Desa Widodomartani, Kecamatan Ngemplak, Kabupaten Sleman ”,” pp. 1–10, 2017.