[Submitted on 29 Jul 2026]

View PDF HTML (experimental)

Abstract:科学论文通常使用合成的、均匀分布的边权重来评估并行单源最短路径 (SSSP) 算法。然而，真实世界图通常呈现出截然不同的、常为重尾的权重分布。这导致算法评估方式与实际性能之间存在脱节，因为大多数 SSSP 实现本质上依赖于权重分布进行参数调优和工作效率优化。本文探讨当前基准测试方法是否无意中影响了这些算法的性能结果。为此，我们对来自不同领域的 17 个真实世界图的权重分布进行了统计表征，并与文献中使用的六种合成分布进行了对比。通过对七种最先进的并行 SSSP 算法进行全面评估，我们展示了算法对边权重的严重敏感性，并证明使用合成均匀权重进行评估会改变最优参数配置，甚至可能颠倒性能排序。这些发现挑战了现有的基准测试标准，并为严谨的 SSSP 算法设计提供了实用见解。

Submission history

From: Marco D'Antonio [view email]
[v1] Wed, 29 Jul 2026 12:15:35 UTC (919 KB)