[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)