可复现 SLF-Killer 图及性能优化实验 #4632
Description
您好 ，
我近期在研究图算法性能极限，尤其关注 SPFA-SLF 在负权图上的最坏情况。为此，我构造了一类可稳定复现的 SLF-Killer 图结构（多跳负权 + 正回边震荡链），该结构会持续触发 SPFA-SLF 的队列误前送与震荡问题。
在该类图上，我测试了 SPFA-SLF 与自己开发的原型算法 JFR，部分测试结果如下：
- 1,000 节点：SPFA-SLF 116.94 ms / 5,825,085 次松弛；JFR 33.16 ms / 175,261 次松弛 → 加速 3.5×
- 10,000 节点：SPFA-SLF 3,692.72 ms / 172,614,311 次松弛；JFR 268.06 ms / 1,191,920 次松弛 → 加速 13.7×
- 50,0000 节点：SPFA-SLF 约 2,540,664.68 ms (~42 分钟) / 93,295,674,368 次松弛；JFR 19,522.09 ms / 74,102,531 次松弛 → 加速 130×
- 100,000 节点：SPFA-SLF 9,885.89 ms / 416,604,533 次松弛；JFR 3,825.38 ms / 15,720,612 次松弛 → 加速 2.58×
算法特点及瓶颈：
- 跳过震荡区段保持局部稳定
- 在负权密集、多跳边图上性能显著优于 SPFA-SLF
- 超大规模图 (>50万节点、数十亿边) 仍需优化内存访问与并行处理
- 算法可进一步结合并行或增量松弛策略提速
该图结构可作为 SPFA-SLF 类算法的最坏情况检测器、图计算系统压力测试及负权系统稳定性验证基准。
如果您对这套算法或压力图生成器感兴趣，我可以提供小规模测试示例，并非常希望能听到您的建议或意见。
此致
敬礼
Jerry
2025年11月25日