Visualisasi Dan Perbandingan Efisiensi Algoritma A*, Greedy, Dan Dijkstra Dalam Mencari Rute Terpendek Di Kota Medan Menggunakan Openstreetmap

Paris  Alvito; Muhammad Ikhsan

doi:10.30865/jurikom.v12i4.8869

Authors

Paris Alvito Universitas Islam Negeri Sumatera Utara, Medan
Muhammad Ikhsan Universitas Islam Negeri Sumatera Utara, Medan

DOI:

https://doi.org/10.30865/jurikom.v12i4.8869

Keywords:

Algoritma A*, Algoritma Dijkstra, Algoritma Greedy, OpenStreetMap, Visualisasi, Shortest Path Search

Abstract

This study compares the efficiency of A*, Greedy, and Dijkstra algorithms in finding the shortest path on the road network of Medan City using geospatial data from OpenStreetMap. An interactive visualization system was developed using web-based technologies such as React.js, MapLibre GL, and Deck.gl to display the pathfinding process in real-time. The evaluation was conducted on two graph scales using six parameters: execution time, number of explored nodes, path length, memory usage, number of nodes in the path, and scalability. The results show that the A* algorithm is the most efficient overall, achieving 0.13 seconds with 17 nodes explored on the small graph, and 0.29 seconds with 52 nodes on the large graph. Dijkstra yields the most accurate paths but with significantly more node exploration and memory consumption, while Greedy is the fastest (0.11 seconds) but less accurate. This research contributes to the understanding of pathfinding algorithms and their implementation in map-based systems.

References

J. Y. Pratama, “Analisis Perbandingan Algoritma Dijkstra dan A-Star dalam Menentukan Rute Terpendek,” JIMUJurnal Ilm. Multidisipliner, vol. 2, no. 03, pp. 668–682, 2024, doi: 10.70294/jimu.v2i03.423.

N. R. I, M. Z. Hilmi, E. Proborini, and F. A. Husain, “Pencarian Rute Terpendek dengan Algoritma Dijkstra Shortest Route Search with Dijkstra ’ s algorithm Shortest Route Search with Dijkstra ’ s Algorithm Shortest Route Search with Dijkstra ’ s algorithm,” vol. 6, no. 1, pp. 50–57, 2025.

M. Ikhsan and Haris, “Ekowisata Rammang-Rammang Sebagai Laboratorium Pembelajaran Kontekstual Geografi Di Kabupaten Maros,” Jambura Geo Educ. J., vol. 3, no. 2, pp. 43–51, 2022, doi: 10.34312/jgej.v3i2.15366.

T. Dealva Arsyad, I. Agi Berutu, E. Keisha Silalahi, and D. Yandra Niska, “Implementasi Algoritma a* (a - Star) Untuk Optimasi Jalur Bus Listrik Di Kota Medan Dengan Visualisasi 2D,” JATI (Jurnal Mhs. Tek. Inform., vol. 9, no. 4, pp. 6138–6143, 2025, doi: 10.36040/jati.v9i4.14001.

N. F. Lakutu, S. L. Mahmud, M. R. Katili, and N. I. Yahya, “Algoritma Dijkstra dan Algoritma Greedy Untuk Optimasi Rute Pengiriman Barang Pada Kantor Pos Gorontalo,” Euler J. Ilm. Mat. Sains dan Teknol., vol. 11, no. 1, pp. 55–65, 2023, doi: 10.34312/euler.v11i1.18244.

N. Sugianti, A. Mardhiyah, and N. R. Fadilah, “Komparasi Kinerja Algoritma BFS, Dijkstra, Greedy BFS, dan A* dalam Melakukan Pathfinding,” JISKA (Jurnal Inform. Sunan Kalijaga), vol. 5, no. 3, pp. 194–204, 2020, doi: 10.14421/jiska.2020.53-07.

F. L. Tobing, F. A. T. Tobing, and Prayogo, “Analisis Perbandingan Algoritma Dfs, Bfs Dan Dijkstra Untuk Menentukan Rute Terpendek Pada Peta Geografis,” J. Widya, vol. 3, no. 1, pp. 59–67, 2022, [Online]. Available: https://jurnal.amikwidyaloka.ac.id/index.php/awl

A. Bonifasius Simbolon, D. Aulia Artika, Y. Christian Sitanggang, and P. Harliana, “Implementasi Algoritma Dijkstra Dalam Menganalisis Rute Terpendek Dan Efisiensi Jarak Tempuh Dari Stasiun Kereta Api Medan Menuju 6 Kampus Di Area Medan Estate,” JATI (Jurnal Mhs. Tek. Inform., vol. 9, no. 1, pp. 162–168, 2025, doi: 10.36040/jati.v9i1.12155.

E. Rahmawati and C. Agustina, “Implementasi Algoritma Greedy dan Djikstra untuk Efektifitas Rute Pariwisata Populer di Borobudur,” J. Teknol. Inf. dan Terap., vol. 8, no. 2, pp. 72–75, 2021, doi: 10.25047/jtit.v8i2.216.

R. A. M. P. N. Hikmah, “Perbandingan Algoritma a Star Dan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Kantor Pos Di Provinsi Lampung,” NBER Work. Pap., p. 39, 2023, [Online]. Available: http://www.nber.org/papers/w16019

J. Dima, M. S. Hamzah, C. G. Tallo, and D. Y. A. Fallo, “Tinjauan Literatur tentang Pemanfaatan Algoritma Greedy untuk Pencarian Jalur Terpendek,” vol. 7, no. 01, pp. 519–528, 2025.

H. Sulaiman, Y. Yuliani, E. Fitri, N. Herlinawati, and S. Watmah, “Algoritma Dijkstra untuk Pendistribusian Carica Nida Food Wonosobo,” J. Sist. dan Teknol. Inf., vol. 8, no. 2, p. 203, 2020, doi: 10.26418/justin.v8i2.38223.

A. Maghfirotul Inayah, N. Cintya Resti, and N. Fadilatul Ilmiyah, “Analisa Perbandingan Algoritma Floyd-Warshalldan Algoritma Dijkstrauntuk Penentuanrute Terdekat,” J. Ilm. Mat. Realis. (JI-MR, vol. 4, no. 2, pp. 146–155, 2023.

A. Dwi Rifka Setyawan, J. Dedy Irawan, and A. Faisol, “Rancang Bangun Aplikasi Penentuan Rute Terpendek Distribusi Jamu Tradisional Menggunakan Metode a*,” JATI (Jurnal Mhs. Tek. Inform., vol. 7, no. 4, pp. 2218–2225, 2023, doi: 10.36040/jati.v7i4.7450.

Alia, M. A. Irwansyah, and H. Novriando, “Aplikasi WebGis Fasilitas Umum Menggunakan Library Leaflet dan OpenStreetMap,” J. Sist. dan Teknol. Inf., vol. 9, no. 3, p. 334, 2021, doi: 10.26418/justin.v9i3.44442.

H. Hendra and Y. F. Riti, “Perbandingan Algoritma Dijkstra Dan Floyd-Warshall Dalam Menentukan Rute Terpendek Stasiun Gubeng Menuju Wisata Surabaya,” JIKA (Jurnal Inform., vol. 6, no. 3, p. 297, 2022, doi: 10.31000/jika.v6i3.6528.

R. Perayoga, P. Hendradi, and A. Setiawan, “Implementasi Algoritma Dijkstra Pada Pencarian Rute Terpendek Objek Wisata,” KLIK Kaji. Ilm. Inform. dan Komput. , vol. 4, no. 3, pp. 1471–1482, 2023, doi: 10.30865/klik.v4i3.1495.

J. S. Iskandar and Y. F. Riti, “Perbandingan Algoritma Greedy dan Algoritma Dijkstra dalam Pencarian Rute Terpendek dari Kabupaten Tuban ke Kota Surabaya,” J. PETIK, vol. 8, no. 2, pp. 96–106, 2022.

C. T. S. Garingging, S. L. Gaol, M. A. Lubis, F. T. Sianturi, B. M. Sembiring, and S. P. Sipayung, “Implementasi Algoritma Dijkstra dalam Menentukan Rute Terpendek dari Unika St. Thomas Medan ke Lapangan Merdeka,” J. Minfo Polgan, vol. 14, no. 1, pp. 789–800, 2025, doi: 10.33395/jmp.v14i1.14892.

S. Skiena, “The Algorithm Design Manual 3rd edition,” in Algorithms and applications, vol. 42, C. Springer, Ed., Stony Brook University, 2020, p. 823. [Online]. Available: http://www.springer.com/series/3191%0Ahttp://www.ncbi.nlm.nih.gov/pubmed/20549881