Comparative Performance Analysis of Some Priority Queue Variants in Dijkstra’s Algorithm

Efficient shortest-path computation in weighted graphs is essential in domains like networking and logistics. Dijkstra’s algorithm depends heavily on the choice of priority queue, and while theoretical complexities are well-documented, their real-world performance varies. This study compares three priority queue implementations-Binary Heap, Fibonacci Heap, and Binomial Heap- within Dijkstra’s algorithm using road network data from Zenodo (https://doi.org/10.5281/zenodo.1290209). The dataset was preprocessed, normalized, and converted into a usable format using MATLAB (R2024b). Theoretical time complexities for core operations—insert, decrease-key, and extract-min—were analyzed. Experiments conducted on synthetically generated graphs showed Binary Heap achieved the fastest execution time (0.00126s) and highest throughput (3313 edges/sec), outperforming Fibonacci and Binomial Heaps. Results indicate that Binary Heap is the optimal choice for execution speed and throughput, especially for large or dense graphs. The findings provide practical guidance for selecting priority queues in real-world shortest-path applications and contribute to the empirical evaluation of data structures in algorithm design.

Shortest path, Dijkstra algorithm, Priority queue, Binary heap, Binomial Heap and Fibonacci heap

1. Abhinau Jauhri (2013): Binomial and Fibonacci heaps in rocket (rkt heaps), abhinaujauhri@gmail.com. [Google Scholar] [Crossref]

2. Akhilesh Kumar Srivastava (2020}: A Practical approach to Data Structure and Algorithm with Programming C: https://searchwork.stanford.edu. [Google Scholar] [Crossref]

3. Buyue, W. (2016). Performance Evaluation of Path finding Algorithms. University Thesis. [Google Scholar] [Crossref]

4. David Epstein (1998). Finding the K shortest path. SIAM Journal on computing – Vol. 28 iss.2 (1998). https://doi.org/10.1137/5009753 9795.290 477. [Google Scholar] [Crossref]

5. Daniel Dominic Sleator and Robert Endrre Tanjan (1986); Self balancing heaps. SIAM J. compt. 15(1); 52-69, Feb. 1986. [Google Scholar] [Crossref]

6. Donald B. Johnson (1977). Efficient algorithm for shortest paths in sparse networks, J. ACM, 24 (1); 1-13 [Google Scholar] [Crossref]

7. Edsger W. Dijkstra: A note on two problems in connection with graphs Numerical mathematics 1:269-271.1959.14,72. [Google Scholar] [Crossref]

8. Elwira Johansson (2020); Practical complexity of the Fibonacci heaps in simulation and modeling framework. Department of Information Technology IT 20084 Uppsata University, post address Box 536, 75121 Uppsala. https://www.teknat.uu.se/ student. [Google Scholar] [Crossref]

9. Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683. [Google Scholar] [Crossref]

10. Gerth Stolting et--al (2012). Strict Fibonacci heaps; In processing of the 44th symposium on theory of computing STOC 12, pages 1177 – 1184, New York NY USA, ACM. 23 [Google Scholar] [Crossref]

11. James B. Orlin (2010). A faster algorithm for the single source shortest path problem with few distinct positive lengths J. of Discrete Algorithms, 8(2): 189- 198 [Google Scholar] [Crossref]

12. James R, Driscoll et-al (1988); Relaxed heaps; an alternative for Fibonacci heaps with applications to parallel computation commu. ACM 31(11); 1343 1354, Nov. 1988.23; MIT Open Access: https://dx.doi.org/10.1016/j.jda.2009.03.001. [Google Scholar] [Crossref]

13. Jiri Vyskocil, Radek Marik (2013) Advance algorithms; binary heap, d-ary heap, binomial heap, Amortized analysis, Fibonacci heap [Google Scholar] [Crossref]

14. Kahneman, D. (2011). Thinking, Fast and Slow. Farrar, Straus and Giroux. [Google Scholar] [Crossref]

15. Ritesh Bhat et-al (2023); Comparative analysis of Bellman-Ford ana Dijkstra’s algorithms for optical evaluation route planning in multi-floor buildings. Article; https://doi.org/10.1080/23311916.2024.23 19394 [Google Scholar] [Crossref]

16. Martell, E., & Sandberg, J. (2016). Evaluation of A* and its variants in path finding. Computational Intelligence Journal, 14(6), 301–320. [Google Scholar] [Crossref]

17. Mikkel Thorup (2003). Integer priority queues with decrease key in constant time and the sole source shortest paths problem. In preceding of the thirty-fifth annual ACM symposium on theory of complexity. STOC ’03 pages 149 158 New York, NY, USA [Google Scholar] [Crossref]

18. Natick M. (2024): Matrix Laboratory (R2024b) programming language. https://www.mathworks,com. [Google Scholar] [Crossref]

19. Rhyd Lewis (2023): A Comparison of Dijkstra’s Algorithm using Fibonacci Heap, Binary Heap, and self-balancing binary trees. Using C++ Implementations of these algorithms Variants School of mathematics, Cardiff University, Cardiff, Wales. Lewis R9 @cf/ac.uk http://www:rhyd.lewis.eu or https://doi.org/10.48550/arX.v.2303.10034 [Google Scholar] [Crossref]

20. Rillet, S. (2006). Shortest paths in edge-weighted graphs. Journal of Applied Mathematics, 45(3), 254–267. [Google Scholar] [Crossref]

21. Samah, H. (2020). Comparative analysis of Dijkstra and Bellman Ford algorithms in shortest path optimization. International Journal of Computational Theory and Engineering, 12(4), 100–108. [Google Scholar] [Crossref]

22. Santoso, P. (2010). Comparative performance of Dijkstra, A*, and ant algorithms. International Journal of Computer Science and Applications, 12(2), 125–134. [Google Scholar] [Crossref]

23. Siddhartha Sen Bernhard Haeuppler and Robert E. Tarjan. On Rank- pairing Heap. SIAM J. Compute. 40 96); 146314485, 2011.23 [Google Scholar] [Crossref]

24. Sneha Sawlani (2017) “Explaining the performance of Bi-directional Dijkstra and A* on a road networks. Electronic theses and Dissertation.1303. University of Denver. https://digitalcommons.du.edu/etd/1303. [Google Scholar] [Crossref]

25. Sunita Deepak Garg (2018) Dynamiting Dijkstra: A solution to Dynamic shortest path problem through Retroactive Priority Queue; Journal of King Saud University; Computer and Information Science 33(4) [Google Scholar] [Crossref]

26. Zenodo. (2018). Road network graphs for betweenness centrality algorithm. [Dataset]. Zenodo. https://doi.org/10.5281/zenodo.1290209 [Google Scholar] [Crossref]

27. Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65. S2CID 14986297 [Google Scholar] [Crossref]

• What the Desert Fathers Teach Data Scientists: Ancient Ascetic Principles for Ethical Machine-Learning Practice
• Comparative Analysis of Some Machine Learning Algorithms for the Classification of Ransomware
• Transfer Learning in Detecting E-Assessment Malpractice from a Proctored Video Recordings.
• Dual-Modal Detection of Parkinson’s Disease: A Clinical Framework and Deep Learning Approach Using NeuroParkNet
• Real-Time Traffic Signal Optimisation Using Deep Q-Network Algorithm and Camera Data