Analisis Kebenaran dan Efisiensi Algoritma Dijkstra VS A-Star (A*) Dalam Penentuan Rute Tercepat ada Graf Berbobot
DOI:
https://doi.org/10.57235/smash.v3i1.8329Keywords:
Algoritma Dijkstra, Algoritma A*, Graf Berbobot, Rute Terpendek, Efisiensi AlgoritmaAbstract
Studi ini menganalisis kebenaran dan efisiensi algoritma Dijkstra dan A* dalam menentukan jalur terpendek pada graf berbobot. Kebenaran dibuktikan secara teoritis menggunakan pendekatan invarian loop untuk Dijkstra dan sifat admissible pada heuristik A*, serta dikonfirmasi melalui eksperimen komputasi. Efisiensi dianalisis berdasarkan kompleksitas waktu dan pengujian empiris meliputi waktu eksekusi, jumlah simpul yang dikunjungi, dan ukuran antrian prioritas. Pengujian dilakukan pada tiga skenario graf berbobot dengan ukuran berbeda menggunakan metode Random Geometric Graph. Hasil menunjukkan bahwa kedua algoritma memiliki tingkat kebenaran 100% dalam seluruh pengujian. Dari segi efisiensi, algoritma A* menunjukkan performa yang lebih cepat dan mampu mengurangi jumlah eksplorasi simpul secara signifikan dibandingkan Dijkstra. Namun, A* memiliki penggunaan memori yang lebih tinggi pada graf berukuran besar. Penelitian ini menyimpulkan bahwa A* lebih unggul dalam efisiensi waktu ketika tersedia heuristik yang valid, sementara Dijkstra lebih stabil ketika heuristik tidak tersedia.
Downloads
References
A. Ardiansyah, A. M. Nasution, and M. Iqbal, “Comparative Analysis of Dijkstra and A* Algorithms for Determining the Shortest Route,” bit-Tech, vol. 8, no. 2, pp. 2974–2983, Dec. 2025, doi: 10.32877/bt.v8i2.3474.
G. Pradeep Reddy, Y. V. P. Kumar, M. Kalyan Chakravarthi, and A. Flah, “Refined Network Topology for Improved Reliability and Enhanced Dijkstra Algorithm for Optimal Path Selection during Link Failures in Cluster Microgrids,” Sustainability (Switzerland), vol. 14, no. 16, Aug. 2022, doi: 10.3390/su141610367.
B. Şeyh, S. Kayali, U. Yuzgec, and M. Ozalp, “Bilecik Şeyh Edebali Üniversitesi Fen Bilimleri Dergisi Autonomous UAV Navigation in Simulated Environments: A Comparative Study of Dijkstra and A* Algorithms Benzetim Yapılan Ortamlarda Otonom İHA Navigasyonu: Dijkstra ve A* Algoritmalarının Karşılaştırmalı Çalışması.” [Online]. Available: https://dergipark.org.tr/tr/pub/bseufbd.
Y. Liu, X. Gao, B. Wang, J. Fan, Q. Li, and W. Dai, “A passage time–cost optimal A* algorithm for cross-country path planning,” International Journal of Applied Earth Observation and Geoinformation, vol. 130, Jun. 2024, doi: 10.1016/j.jag.2024.103907.
Md. Mehedi Hassan, Md. Asadujjaman, and Md. Golam Robbani, “A Modified Approach of Dijkstra’s Method for Finding Shortest Path in a Weighted Directed Graph,” American Journal of Science, Engineering and Technology, Jul. 2023, doi: 10.11648/j.ajset.20230803.14.
S. S. Abed and S. F. Noaman, “Comparative Analysis of Shortest Path Algorithms,” South Asian Research Journal of Engineering and Technology, vol. 7, no. 05, pp. 131–143, Dec. 2025, doi: 10.36346/sarjet.2025.v07i05.002.
R. Lewis, “Algorithms for finding shortest paths in networks with vertex transfer penalties,” Algorithms, vol. 13, no. 11, pp. 1–21, Nov. 2020, doi: 10.3390/a13110269.
K. Nosirov, E. Norov, dan S. Tashmetov, “A Review of Shortest Path Problem in Graph Theory,” Eurasian Journal of Engineering and Technology, vol. 13, pp. 1–11, Dec. 2022.
A. Mohan, W. X. Leow, and A. Hobor, “Functional Correctness of C Implementations of Dijkstra’s, Kruskal’s, and Prim’s Algorithms,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Science and Business Media Deutschland GmbH, 2021, pp. 801–826. doi: 10.1007/978-3-030-81688-9_37.
R. Duan, J. Mao, X. Mao, X. Shu, and L. Yin, “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths,” Jul. 2025, [Online]. Available: http://arxiv.org/abs/2504.17033
I. H. Toroslu, “Improving The Floyd-Warshall All Pairs Shortest Paths Algorithm,” Sep. 2021, [Online]. Available: http://arxiv.org/abs/2109.01872.
S. Basu, N. Kōshima, T. Eden, O. Ben-Eliezer, and C. Seshadhri, “A Sublinear Algorithm for Approximate Shortest Paths in Large Networks,” Jun. 2024, [Online]. Available: http://arxiv.org/abs/2406.08624.
A. Bernstein, D. Nanongkai, and C. Wulff-Nilsen, “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” Journal of the ACM, vol. 72, no. 4, Jul. 2025, doi: 10.1145/3742890.
I. Szcześniak, B. Woźna-Szcześniak, and I. Olszewski, “Generic Dijkstra,” Mar. 2026, doi: 10.1109/NOMS56928.2023.10154322.
D. Rachmawati and L. Gustin, “Analysis of Dijkstra’s Algorithm and A∗ Algorithm in Shortest Path Problem,” in Journal of Physics: Conference Series, Institute of Physics Publishing, Jul. 2020. doi: 10.1088/1742-6596/1566/1/012061.
Y. W. Shin et al., “Near-optimal weather routing by using improved A* algorithm,” Applied Sciences (Switzerland), vol. 10, no. 17, Sep. 2020, doi: 10.3390/app10176010.
J. Vilela, B. Fanzeres, R. Martinelli, and C. Contardo, “Efficient labeling algorithms for adjacent quadratic shortest paths,” Dec. 2021, [Online]. Available: http://arxiv.org/abs/2112.04045.
A. B. A. A. B. R and A. S. A. Ahmed, “Designing and Implementing Shortest and Fastest Paths; A Comparison of Bellman-Ford algorithm, A*, and Dijkstra’s algorithms,” International Journal of Computer Trends and Technology, vol. 69, no. 5, pp. 6–12, May 2021, doi: 10.14445/22312803/ijctt-v69i5p102.
N. Aldhafferi, “Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline,” Computers, vol. 14, no. 12, Dec. 2025, doi: 10.3390/computers14120545.
R. Rusmi and M. Amrin Lubis, “SISTEMASI: Jurnal Sistem Informasi Determining Travel Time and Fastest Route Using Dijkstra Algorithm and Google Map.” [Online]. Available: http://sistemasi.ftik.unisi.ac.id496.
F. Sapundzhi, K. Danev, A. Ivanova, M. Popstoilov, and S. Georgiev, “A Performance Comparison of Shortest Path Algorithms in Directed Graphs †,” Engineering Proceedings, vol. 100, no. 1, 2025, doi: 10.3390/engproc2025100031.
M. R. Wayahdi, S. H. N. Ginting, and D. Syahputra, “Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path,” International Journal of Advances in Data and Information Systems, vol. 2, no. 1, pp. 45–52, Feb. 2021, doi: 10.25008/ijadis.v2i1.1206.
B. Yang et al., “A novel heuristic emergency path planning method based on vector grid map,” ISPRS Int. J. Geoinf., vol. 10, no. 6, Jun. 2021, doi: 10.3390/ijgi10060370.
V. Milin, T. Stanivuk, I. Skoko, and T. Bulić, “Dijkstra and A* Algorithms for Algorithmic Optimization of Maritime Routes and Logistics of Offshore Wind Farms,” J. Mar. Sci. Eng., vol. 13, no. 10, Oct. 2025, doi: 10.3390/jmse13101863.
O. Alamoudi and M. Al-Hashimi, “On the Energy Behaviors of the Bellman–Ford and Dijkstra Algorithms: A Detailed Empirical Study,” Journal of Sensor and Actuator Networks, vol. 13, no. 5, Oct. 2024, doi: 10.3390/jsan13050067.
H. Mehta, P. Kanani, and P. Lande, “Google Maps,” 2019.
Y. F. Riti, J. S. Iskandar, and H. Hendra, “Comparison Analysis of Graph Theory Algorithms for Shortest Path Problem,” Jurnal Sisfokom (Sistem Informasi dan Komputer), vol. 12, no. 3, pp. 415–424, Nov. 2023, doi: 10.32736/sisfokom.v12i3.1756.
S. H. Barkund, A. Sharma, and H. R. Bhapkar, “Survey of Shortest Path Algorithms,” International Journal of Renewable Energy Exchange, vol. 10, no. 11, pp. 46–57, Nov. 2022, doi: 10.58443/ijrex.10.11.2022.46-57.
F. A. S. Alwafi, X. Xu, R. Saatchi, and L. Alboul, “Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm,” Information (Switzerland), vol. 16, no. 6, Jun. 2025, doi: 10.3390/info16060431.
R. D. Saktia Purnama et al., “IMPLEMENTASI PENGGUNAAN ALGORITMA GREEDY BEST FIRST SEARCH UNTUK MENENTUKAN RUTE TERPENDEK DARI CILACAP KE YOGYAKARTA,” Jurnal Informatika dan Teknik Elektro Terapan, vol. 12, no. 2, Apr. 2024, doi: 10.23960/jitet.v12i2.4068.
Downloads
Published
How to Cite
Issue
Section
Citation Check
License
- Authors certify that the work reported here has not been published before and contains no materials the publication of which would violate any copyright or other personal or proprietary right of any person or entity.
- Authors dont transfer or license the copyright of publishing to SMASH: Journal of Social Management Sains and Health Research to publish the article in any media format, to share, to disseminate, to index, and to maximize the impact of the article in any databases.
- Authors hereby dont agree to transfer a copyright for publishing to SMASH: Journal of Social Management Sains and Health Publisher of the manuscript.
- Authors reserve the following:
- all proprietary rights other than copyright such as patent rights;
- the right to use all or part of this article in future works of our own such as in books and lectures;
- use for presentation in a meeting or conference and distributing copies to attendees;
- use for internal training by author's company;
- distribution to colleagues for their research use;
- use in a subsequent compilation of the author's works;
- inclusion in a thesis or dissertation;
- reuse of portions or extracts from the article in other works (with full acknowledgement of final article);
- preparation of derivative works (other than commercial purposes) (with full acknowledgement of final article); and
- voluntary posting on open web sites operated by author or author’s institution for scholarly purposes, but it should follow the open access license of Creative Common CC BY-NC License.
