We present an implementation and a brief experimental analysis of the deterministic algorithm proposed by Duan et al. (2025) for the Single-Source Shortest Path (SSSP) problem, which achieves the best known asymptotic upper bound in the comparison-addition model, with running time $O(m \log^{2/3} n)$. We provide a faithful C++ implementation of this algorithm, following all structural details described in the original paper, and compare its empirical performance with the classical Dijkstra's algorithm using binary heaps. The experiments were conducted on both synthetic sparse random graphs and real-world road network instances from the DIMACS benchmark. Our results show that, despite its superior asymptotic complexity, the new algorithm presents significantly larger constant factors, making Dijkstra's algorithm faster for all tested sparse graph sizes, including instances with tens of millions of vertices. Our implementation achieves $O(m \log^{2/3} n)$ expected time, due to the use of hash tables, and some possibilities for making it worst-case are being considered. (This is a ongoing work.)
翻译：本文介绍了针对单源最短路径（SSSP）问题，由段等人（2025）提出的确定性算法的实现及简要实验分析。该算法在比较-加法模型中达到了已知的最佳渐近上界，运行时间为$O(m \\log^{2/3} n)$。我们提供了该算法的忠实C++实现，严格遵循原论文描述的所有结构细节，并将其经验性能与使用二叉堆的经典Dijkstra算法进行比较。实验在合成稀疏随机图以及来自DIMACS基准测试的真实道路网络实例上进行。结果表明，尽管新算法具有更优的渐近复杂度，但其常数因子显著更大，使得在所有测试的稀疏图规模（包括顶点数达数千万的实例）中，Dijkstra算法均更快。由于使用了哈希表，我们的实现达到了$O(m \\log^{2/3} n)$的期望时间，目前正在考虑使其达到最坏情况性能的可能性。（这是一项进行中的工作。）
相关内容
微信扫码咨询专知VIP会员