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.

单源最短路径（Single-source shortest path，简称SSSP）的发现，是算法图论中一类最短路径问题中的组合优化问题。解决SSSP问题的诸多命题大多依赖于Dijkstra算法。尽管在理论上的渐近时间复杂度上存在劣势，但在实际中，Dijkstra算法的二进制变体在处理现实数据集的SSSP计算中，尤其是在稀疏输入图中，实证上优于斐波那契变体。本文深入探讨了Dijkstra算法变体在理论上声称的渐近时间复杂度与实证效率结果之间的差异背后的原因。我们考察了现实世界的图数据集存储库，对Dijkstra算法变体的最佳情况时间复杂度进行了理论分析，比较了最佳情况和最坏情况的时间复杂度，在现实数据集上对最先进的变体进行了实验测试，并统计了减少键操作调用次数。最终，我们得出结论，最佳情况时间复杂度界限O(V log V)描绘了一幅更为真实的图景，并弥合了声称的理论渐近时间复杂度与观察到的Dijkstra算法变体的实证效率结果之间的差距。