我正在使用约翰逊算法来检测给定图中的负循环。我遇到的问题是，当在虚拟节点上运行 Bellman-Ford 时，每次权重更新都是浮点运算，这通常会导致一些精度误差。我正在处理的图平均有 250k 个顶点和 500k 个边，这意味着相当多的浮点运算和累积的精度误差。
在我实际根据 Bellman-Ford 的结果更新边缘后，出现了很多 -0.000001 类型的错误，并且我能够检测并修复它们。但结果图中甚至有一些因微小错误而累积的 -1 权重。我可以在不大幅降低性能的情况下解决这个问题吗？
嗯，最简单的方法是使用定点（整数）权重。如果缩放权重以使最大量级权重为 1^63 不会给最小量级权重添加不可接受的误差，则执行此操作。
否则，使用成对求和或卡汉求和来最小化误差可能就足够了。在极端情况下，您可以使用多精度浮点技术来完全消除它，但我的直觉是，需要一个奇怪的巨大图表（比您的大得多）才能成为必要的。