Analisis Keterbatasan Algoritma Dijkstra dalam Menentukan Jalur Terpendek pada Graph

Authors

  • Ananda Syafika Universitas Negeri Medan, Indonesia
  • Febrianta Immanuel Purba Universitas Negeri Medan, Indonesia
  • M Farel Revansha Buulolo Universitas Negeri Medan, Indonesia
  • Nayla Luthfiah Hanan Universitas Negeri Medan, Indonesia
  • Adidtya Perdana Universitas Negeri Medan, Indonesia

DOI:

https://doi.org/10.57235/smash.v3i1.8252

Keywords:

Algoritma Dijkstra, Shorstest Path, Graph Berbobot, Kompleksitas Algoritma, Greedy Algorithm

Abstract

Penelitian ini bertujuan untuk menganalisis keterbatasan algoritma Dijkstra dalam menentukan jalur terpendek pada graph berbobot. Metode penelitian yang digunakan adalah studi literatur dengan pendekatan deskriptif-analisis yang berfokus pada analisis teoritis terhadap prinsip kerja algoritma, kompleksitas komputasi, serta kondisi-kondisi yang mempengaruhi keoptimalan solusi. Hasil kajian menunjukkan bahwa algoritma Djikstra bekerja optimal pada graph statis dengan bobot sisi non-negatif dan memenuhi sifat greedy choice serta optimal substucture. Namun, algoritma ini memiliki beberapa keterbatasan utama, yaitu tidak mampu menangani bobot negatif, tidak dapat mendeteksi negative cycle, serta mengalami penurunan efisiensi pada graph berskala besar dan dinamis. Selain itu, keputusan greedy yang bersifat final menyebabkan algoritma tidak dapat merevisi solusi ketika ditemukan jalur yang lebih pendek pada kondisi tertentu. Oleh karena itu, pemilihan algoritma shortest path harus disesuaikan dengan karakteristik graph dan kebutuhan komputasi. Penelitian ini memberikan pemahaman konseptual mengenai batasan operasional algoritma Djikstra sebagai dasar pemilihan metode yang tepat dalam penyelasaian masalah jalur terpendek.

Downloads

Download data is not yet available.

References

Aldhafferi, N. (2025). Time and memory trade-offs in shortest-path algorithms across graph topologies: A*, Bellman–Ford, Dijkstra, AI-augmented A* and a neural baseline. Computers, 14, 545.

Amin, A., & Hendrik, B. (2023). Analisis penerapan algoritma Dijkstra dalam optimasi penentuan rute: Sebuah kajian literatur sistematis. Journal of Education Research, 6(1).

Angul, A., Fallo, D., Tanggo, K. V., Belo, I. N. A., & Hoar, F. (2025). Implementasi algoritma Dijkstra dan Greedy dalam penyelesaian masalah rute terpendek. Jurnal Kridatama Sains dan Teknologi, 7(01), 489–496.

Asmiati, P., Prawinasti, K., Damayanti, M., & Yulianti, L. (2025). The locating chromatic number of (k, n)-split cycle graph and its barbell operation. Electronic Journal of Graph Theory and Applications, 13(2), 249–258.

Bhaskara, I. M. A., Kumara, I. M. S., Darma, I. G. W., & Raharja, I. K. A. W. (2024). Perbandingan algoritma Dijkstra dan Floyd-Warshall menggunakan software defined network untuk rute terpendek. RESISTOR, 7(1), 109–118.

Chen, R. (2022). Dijkstra's shortest path algorithm and its application on bus routing. In Proceedings of the 2022 International Conference on Urban Planning and Regional Economy (UPRE 2022).

Duan, R., Mao, J., Mao, X., Shu, X., & Yin, L. (2025). Breaking the sorting barrier for directed single-source shortest paths. Manuscript.

Durand, A., Watteau, T., Ghazi, G., & Botez, R. M. (2024). Generalized shortest path problem: An innovative approach for non-additive problems in conditional weighted graphs. Mathematics, 12, 2995.

Fedorov, D., Kontsevik, G., Bashirov, R., Mityagin, S., Tupikina, L., Zakharenko, N., & Budennyy, S. (2025). Assessing the complexity of a path search optimization method based on clustering for a transport graph. EPJ Data Science, 14, 32.

Hadi, H. M., & Ibrahim, I. M. (2025). A comprehensive review of shortest path algorithms for network routing. Asian Journal of Research in Computer Science, 18(3), 152–175.

Haritha, T., & Chithra, A. V. (2025). The distance Seidel matrix of connected graphs. AKCE International Journal of Graphs and Combinatorics, 22(3), 241–252.

Hoepner, J. I., MacGillivray, G., & Mynhardt, C. M. (2025). Maximum boundary independent broadcasts in graphs and trees. Electronic Journal of Graph Theory and Applications, 13(2), 237–248.

Iranmanesh, M. A., & Moghaddami, N. (2025). Some properties of Cayley signed graphs on finite Abelian groups. Electronic Journal of Graph Theory and Applications, 13(2), 417–422.

Jelita, F., Fallo, D., & Miru, Y. G. (2025). Optimalisasi rute menggunakan algoritma Dijkstra dan Greedy: Sebuah pendekatan komparatif. Jurnal Kridatama Sains dan Teknologi, 7(01), 555–562.

Kalita, J., & Paul, S. (2025). On adjacency and (signless) Laplacian spectra of centralizer and co-centralizer graphs of some finite non-abelian groups. Electronic Journal of Graph Theory and Applications, 13(2), 397–416.

Kamyab, K., Ghasemi, M., & Varmazyarb, R. (2025). Minimally 4-restricted edge connected graphs. Electronic Journal of Graph Theory and Applications, 13(2), 375–382.

Kim, K. (2025). The Italian bondage and reinforcement numbers of digraphs. Electronic Journal of Graph Theory and Applications, 13(2), 361–374.

Korivand, M., Soltankhah, N., & Khashyarmanesh, K. (2025). Uniquely proper distinguishing colorable graphs. Electronic Journal of Graph Theory and Applications, 13(2), 423–440.

Lewis, R. (2020). Algorithms for finding shortest paths in networks with vertex transfer penalties. Algorithms, 13, 269.

Liu, Y., Lin, Q., Hong, B., Peng, Y., Hjerpe, D., & Liu, X. (2023). Resonance algorithm: An intuitive algorithm to find all shortest paths between two nodes. Complex & Intelligent Systems, 9, 4159–4167.

Madkour, A., Aref, W. G., Rehman, F. U., Rahman, M. A., & Basalamah, S. (2017). A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044.

Mane, S. A., & Shinde, N. V. (2025). Quasi perfect codes in the cartesian product of some graphs. Electronic Journal of Graph Theory and Applications, 13(2), 441–458.

Mojdeh, D. A., & Samadzadeh, M. R. (2025). Perfect coalition in graphs. Electronic Journal of Graph Theory and Applications, 13(2), 345–360.

More, R. D., Patil, A. S., Dandwate, D. S., & Tupe, U. J. (2021). A literature review on applications of graph theory in various fields. IJRTI, 6(1), 1–8.

Musridho, R. J., Rusnedy, H., & Sudirman, W. F. R. (2025). Analisis komparatif algoritma Dijkstra dan Google Maps API dalam penentuan rute tercepat. Journal of Artificial Intelligence and Digital Business (RIGGS), 4(3), 5017–5022.

Pancahayani, S., Simanjuntak, R., Baca, M., Semanicova-Fenovcíkova, A., & Uttunggadewa, S. (2025). On the relations among edge magic total, edge antimagic total, and ASD-antimagic graphs. Electronic Journal of Graph Theory and Applications, 13(2), 387–396.

Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem. Journal of Physics: Conference Series, 1566(1).

Riti, Y. F., Iskandar, J. S., & Hendra. (2023). Comparison analysis of graph theory algorithms for shortest path problem.

Salsabila, T. N., Chaerani, D., & Napitupulu, H. (2026). Systematic literature review of GPS-based multi-objective environmentally friendly shortest path with a proposed lexicographic framework. CAUCHY – Jurnal Matematika Murni dan Aplikasi, 11(1), 364–381.

Sinlae, D. A., Ledoh, P. K., & Fallo, D. (2025). Analisis algoritma Dijkstra dan Greedy pada pencarian jalur terpendek di graf berbobot. Jurnal Penelitian Multidisiplin Terpadu, 9(6), 282–286.

Young, N. E., Tarjan, R. E., & Orlin, J. B. (1991). Faster parametric shortest path and minimum balance algorithms. Networks, 21(2).

Downloads

Published

2026-04-16

How to Cite

Syafika, A., Purba, F. I., Buulolo, M. F. R., Hanan, N. L., & Perdana, A. (2026). Analisis Keterbatasan Algoritma Dijkstra dalam Menentukan Jalur Terpendek pada Graph. SMASH: Journal of Social Management Sains and Health, 3(1), 21–34. https://doi.org/10.57235/smash.v3i1.8252

Issue

Vol. 3 No. 1 (2026): April 2026

Section

Articles

Citation Check

License

  1. 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.
  2. 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.
  3. Authors hereby dont agree to transfer a copyright for publishing to SMASH: Journal of Social Management Sains and Health Publisher of the manuscript. 
  4. Authors reserve the following: 
    1. all proprietary rights other than copyright such as patent rights; 
    2. the right to use all or part of this article in future works of our own such as in books and lectures;
    3. use for presentation in a meeting or conference and distributing copies to attendees; 
    4. use for internal training by author's company;
    5. distribution to colleagues for their research use;
    6. use in a subsequent compilation of the author's works;
    7. inclusion in a thesis or dissertation;
    8. reuse of portions or extracts from the article in other works (with full acknowledgement of final article);
    9. preparation of derivative works (other than commercial purposes) (with full acknowledgement of final article); and
    10. 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.