Evaluating the Influence of Graph Density on the Efficiency of Shortest Path Algorithms Using Different Data Structures

Velin Kralev; Radoslava Kraleva; Aleksandra Popova

doi:10.3991/ijim.v20i13.61989

Authors

Velin Kralev South West University "Neofit Rilski", Blagoevgrad, Bulgaria https://orcid.org/0000-0002-7780-8281
Radoslava Kraleva South West University "Neofit Rilski", Blagoevgrad, Bulgaria https://orcid.org/0000-0003-3322-7298
Aleksandra Popova South West University "Neofit Rilski", Blagoevgrad, Bulgaria https://orcid.org/0009-0008-0257-002X

DOI:

https://doi.org/10.3991/ijim.v20i13.61989

Keywords:

graph theory, shortest path, adjacency matrix, adjacency list, graph density, data structures

Abstract

This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.

Author Biographies

Velin Kralev, South West University "Neofit Rilski", Blagoevgrad, Bulgaria

Velin Kralev is an associate professor of Computer Science at the South-West University “Neofit Rilski” in Blagoevgrad, Bulgaria. He defended his Ph.D. Thesis in 2010. His research interests include graph algorithms, optimization problems in graphs, and component-oriented software engineering.

Radoslava Kraleva, South West University "Neofit Rilski", Blagoevgrad, Bulgaria

Radoslava Kraleva is an associate professor of Computer Science at the South-West University “Neofit Rilski” in Blagoevgrad, Bulgaria. She defended her Ph.D. Thesis in 2014. Her research interests include speech recognition, mobile app development, and computer graphic.

Aleksandra Popova, South West University "Neofit Rilski", Blagoevgrad, Bulgaria

Aleksandra Popova is a student in Information Systems and Technologies at the Faculty of Natural Sciences and Mathematics at South-West University “Neofit Rilski” in Blagoevgrad, Bulgaria. Her research interests focus on graph algorithms, database systems, web design and graphic design, as well as machine learning.

References

[1] H. W. Y. Adoni, T. Nahhal, M. Krichen, B. Aghezzaf, and A. El Byed, "A survey of current challenges in partitioning and processing of graph-structured data in parallel and distributed systems," Distributed and Parallel Databases, 38 (2), pp. 495 - 530, 2020. doi: 10.1007/s10619-019-07276-9

[2] C. H. Tognon, and R. A. Kharabsheh, "Some Properties of the Formal Local Cohomology Module and Application in the Theory of Graphs," Applied Mathematics and Information Sciences, vol. 16, no. 1, pp. 45-49, 2022. doi: 10.18576/amis/160105

[3] S. Balaji, M. S. Obaidat, S. Suthir, M. Rajesh, and K. C. Suresh, "Selection of intermediate routes for secure data communication systems using graph theory application and grey wolf optimization algorithm in MANETs," IET Networks, vol. 10, no. 5, pp. 246-252, 2021. doi: 10.1049/ntw2.12026

[4] H. Yue, H. Lin, Y. Jin, H. Zhang, and K. Cai, "Opening Knowledge Graph Model Building of Artificial Intelligence Curriculum," International Journal of Emerging Technologies in Learning, vol. 17, no. 14, pp. 64-77, 2022. doi: 10.3991/ijet.v17i14.32613

[5] C. M. H. De Figueiredo, "The P versus NP-complete dichotomy of some challenging problems in graph theory," Discrete Applied Mathematics, vol. 160, no. 18, pp. 2681-2693, 2012. doi: 10.1016/j.dam.2010.12.014

[6] N. Gruttemeier, P. H. Keßler, C. Komusiewicz, and F. Sommer, "Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs," Journal of Combinatorial Optimization, vol. 48, no. 3, art. no. 16, 2024. doi: 10.1007/s10878-024-01204-z

[7] T. Li, Y. Su, Z. Yang, and S. Zhang, "Quantum approximate optimization algorithms for maximum cut on low-girth graphs," Physical Review Research, vol. 7, no. 3, art. no. 033014, 2025. doi: 10.1103/jypq-v1fn

[8] A. Tilantera, A. Korhonen, O. Seppälä, and T. Taivainen, "Investigating Students' Misconceptions of Dijkstra's Algorithm: Exploration of Algorithm Simulation Traces," Annual Conference on Innovation and Technology in Computer Science Education. ITiCSE. vol. 1, pp. 674 - 680, 2025. doi: 10.1145/3724363.3729081

[9] O. Asher, S. Dolev, and L.-O. Raviv, "SSPT: Shallowest Shortest Path Tree (Short Paper)," Lecture Notes in Computer Science, vol. 16244 LNCS, pp. 358–371, 2026. doi: 10.1007/978-3-032-10759-6_25

[10] B. Riabenko, O. Martynova, Y. Boyarinova, and A. Krainosvit, "Finding Optimal Routes in Internal Routing Networks based on a Modified Dijkstra’s Algorithm," International Journal of Modern Education and Computer Science, vol. 17, no. 4, pp. 37–47, 2025. doi: 10.5815/ijcnis.2025.04.03

[11] K. Obelovska, O. Tkachuk, and Y. Snaichuk, "Minimizing the Number of Distrustful Nodes on the Path of IP Packet Transmission," Computation, vol. 12, no. 5, art. no. 91, 2024. doi: 10.3390/computation12050091

[12] M. Zhang, M. Sutcliffe, P. I. Nicholson, and Q. Yang, "Efficient Autonomous Path Planning for Ultrasonic Non-Destructive Testing: A Graph Theory and K-Dimensional Tree Optimisation Approach," Machines, vol. 11, no. 12, art. no. 1059, 2023. doi: 10.3390/machines11121059

[13] Z. Grujic and B. Grujic, "Optimal Routing in Urban Road Networks: A Graph-Based Approach Using Dijkstra’s Algorithm," Applied Sciences (Switzerland), vol. 15, no. 8, art. no. 4162, 2025. doi: 10.3390/app15084162

[14] D. Ouyang, D. Wen, L. Qin, L. Chang, X. Lin, and Y. Zhang, "When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks," VLDB Journal, vol. 32, no. 6, pp. 1263–1287, 2023. doi: 10.1007/s00778-023-00789-x

[15] L. Jiang, Y. Lai, Q. Chen, W. Zeng, F. Yang, and F. Fan, "Shortest Path Distance Prediction Based on CatBoost," Lecture Notes in Computer Science, vol. 12999 LNCS, pp. 133–143, 2021. doi: 10.1007/978-3-030-87571-8_12

[16] M. Joswig and B. Schröter, "Parametric Shortest-Path Algorithms via Tropical Geometry," Mathematics of Operations Research, vol. 47, no. 3, pp. 2065–2081, 2022. doi: 10.1287/moor.2021.1199

[17] T. Iwata, K. Kitaura, R. Matsuo, and H. Ohsaki, "A Solution for Finding Quasi-Shortest Path with Graph Coarsening," International Conference on Information Networking, 2022-January, pp. 215–219, 2022. doi: 10.1109/ICOIN53446.2022.9687193

[18] Sunita and D. Garg, "A Retroactive Approach for Dynamic Shortest Path Problem," National Academy Science Letters, vol. 42, no. 1, pp. 25–32, 2019. doi: 10.1007/s40009-018-0674-6

[19] H. Arslan and M. Manguoǧlu, "A hybrid single-source shortest path algorithm," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27, no. 4, pp. 2636–2647, 2019. doi: 10.3906/elk-1901-23

[20] X. Gao, Y. Xianzang, X. You, Y. Dang, G. Chen, and X. Wang, "Reachability for airline networks: fast algorithm for shortest path problem with time windows," Theoretical Computer Science, vol. 749, pp. 66–79, 2018. doi: 10.1016/j.tcs.2018.01.016

[21] M. A. Qureshi, M. F. Hassan, S. Safdar, R. Akbar, A. Ali, and M. K. Ehsan, "Dijkstra’s Algorithm-A Case Study to Understand How Algorithms are improved," VFAST Transactions on Software Engineering, vol. 9, no. 3, pp. 48–56, 2021. doi: 10.21015/vtse.v9i3.706

[22] S. Atalig, A. Hickerson, A. Srivastav, T. Zheng, and M. Chrobak, "Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths," Leibniz International Proceedings in Informatics, LIPIcs, vol. 322, 2024. doi: 10.4230/LIPIcs.ISAAC.2024.8

[23] G. Brodal, "Priority queues with decreasing keys," Theoretical Computer Science, vol. 1000, art. no. 114563, 2024. doi: 10.1016/j.tcs.2024.114563

[24] H. T. T. Binh, T. B. Thang, N. D. Thai, and P. D. Thanh, "A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization," Engineering Applications of Artificial Intelligence, vol. 100, art. no. 104187, 2021. doi: 10.1016/j.engappai.2021.104187

[25] V. Kralev and R. Kraleva, "Combining Genetic Algorithm with Local Search Method in Solving Optimization Problems," Electronics (Switzerland), vol. 13, no. 20, art. no. 4126, 2024. doi: 10.3390/electronics13204126

[26] H. T. T. Binh, P. D. Thanh, and T. B. Thang, "New approach to solving the clustered shortest-path tree problem based on reducing the search space of evolutionary algorithm," Knowledge-Based Systems, vol. 180, pp. 12–25, 2019. doi: 10.1016/j.knosys.2019.05.015

[27] K. Ibrahim Mohammad Ata, A. Che Soh, A. J. Ishak, and H. Jaafar, "Guidance system based on Dijkstra-ant colony algorithm with binary search tree for indoor parking system," Indonesian Journal of Electrical Engineering and Computer Science, vol. 24, no. 2, pp. 1173–1182, 2021. doi: 10.11591/ijeecs.v24.i2.pp1173-1182

[28] V. Kralev, R. Kraleva, and V. Ankov, "An Interactive Application for Learning and Analyzing Different Graph Vertex Cover Algorithms," International Journal of Engineering Pedagogy, vol. 13, no. 1, pp. 4–19, 2023. doi: 10.3991/ijep.v13i1.35661

[29] Y. Li, "Robot path selection based on path planning algorithms in traffic situations," AIP Conference Proceedings, vol. 3144, no. 1, art. no. 030014, 2024. doi: 10.1063/5.0214289

[30] W. Liu, P. Wang, S. Chen, S. Xin, C. Tu, Y. He, and W. Wang, "Towards geodesic ridge curve for region-wise linear representation of geodesic distance field," Computer Aided Geometric Design, vol. 111, art. no. 102291, 2024. doi: 10.1016/j.cagd.2024.102291

[31] H. Yang, "Analysis and study on path planning algorithms in the further mobile action," Journal of Physics: Conference Series, vol. 2824, no. 1, art. no. 012006, 2024. doi: 10.1088/1742-6596/2824/1/012006

[32] u. Wamiliana, R. P. Sari, A. Reformasari, J. Suparman, and A. Junaidi, "Solving the Shortest Total Path Length Spanning Tree Problem Using the Modified Sollin and Modified Dijkstra Algorithms," Science and Technology Indonesia, vol. 8, no. 4, pp. 684–690, 2023. doi: 10.26554/sti.2023.8.4.684-690