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

Abstract

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.