SSSP Problem Dataset

Single-source shortest path (SSSP) discovery, one of a shortest path problem in algorithmic graph theory, is a combinatorial optimization problem. Most propositions solving the SSSP problem rely on Dijkstra’s algorithm. Although theoretically inferior in asymptotic upper bound time complexity, Dijkstra’s algorithm Binary variant outperforms Fibonacci variant empirically, in SSSP computations for real-world datasets, especially on sparse input graphs. This article delved into the underlying reasons behind the disparities between the theoretical asymptotic time complexity claims and empirical efficiency outcomes of Dijkstra’s algorithm variants. We examined real-world graph dataset repositories, performed theoretical time complexity analysis of Dijkstra’s algorithm variants for best-case, compared the best-case and worst-case time complexities, experimentally tested state-of-the-art implementation of the variantson real-world datasets and counted Decrease-key operation calls. Finally, we have concluded that best-case time complexity boundO(V log V)depicts a more realistic picture and bridges the gap between the claimed theoretical asymptotic time complexity and observed empirical efficiency outcomes of Dijkstra’s algorithm variants.