使用Johnson算法重加权时的浮点误差问题求助

针对大规模图（25万顶点、50万边）下Johnson算法的浮点精度问题，以下是几个低性能损耗的解决思路：

1. 彻底规避浮点运算（最优方案） #

如果原始边权是有理数（比如有限小数、分数），将所有边权转换为整数运算：

• 找出所有边权的最小公分母（或最大小数位数），比如所有边权最多保留6位小数，就将所有边权乘以10^6转成整数；
• 整个Bellman-Ford（或SPFA）过程用整数计算h(v)（虚拟节点到各顶点的最短路径）；
• 重新加权时，计算w'(u,v) = w(u,v) + h(u) - h(v)也用整数，最后如果需要还原浮点，再除以之前的倍数即可。
  这种方法完全消除浮点误差，整数运算的性能甚至比浮点更快，几乎没有额外性能损耗。

2. 优化Bellman-Ford的实现减少运算次数 #

用**队列优化的Bellman-Ford（SPFA）**替代原始Bellman-Ford：

• 原始Bellman-Ford需要遍历V-1次所有边，而SPFA仅对松弛过的顶点的出边进行更新，大幅减少浮点运算的总次数，从而降低误差累积；
• 对于稀疏图，SPFA的时间复杂度接近线性，在你的大规模图场景下性能提升明显，同时从根源减少误差来源。

3. 浮点运算的精度控制 #

如果必须使用浮点：

• 优先使用double类型而非float，double的64位精度能大幅减缓误差累积速度，避免小误差快速放大到-1级别的错误；
• 在Bellman-Ford的松弛步骤后，对h(v)进行可控截断：比如将h(v)四舍五入到1e-6或1e-8的精度（根据原始边权的精度需求调整），截断操作的开销极小，且能避免微小误差不断叠加；
• 重新加权后，对w'(u,v)做阈值修正：如果计算结果小于0但绝对值小于设定的误差阈值（比如1e-6），直接将其设为0——因为Johnson算法中，原图无负环时重新加权的边理论上非负，这类微小负值完全是浮点误差导致的。

4. 负环检测的简化逻辑 #

如果你的核心需求只是检测负环而非计算所有点对最短路径，可以简化流程：

• 无需完整计算所有h(v)，只需用SPFA检测是否存在从虚拟节点出发可达的负环（即SPFA中某个顶点入队次数超过V次）；
• 这种情况下，浮点运算的次数更少，误差累积的概率也更低，同时性能更优。

内容的提问来源于stack exchange，提问作者Ahmet Yazıcı