algorithm - 用于正电路的 Bellman-Ford 算法

Question

我正在处理一个有向图的项目，其中边的权重都取决于变量 x。我试图找到 x 的最小值，使我的图形不包含任何正权重电路。

我的问题是 - 这可能很愚蠢，但我不明白 - :如何使用修改后的 Bellman-Ford 来检查是否存在正电路而不是负电路？

谢谢。

Answer 1

How can I use a modified Bellman-Ford to check for the presence of positive circuits instead of negative circuits ?

将所有权重更改为负值:

w'(u,v) = -w(u,v)

然后简单地运行常规 BF。

您可以对该值 x 运行二进制搜索以找到负循环所需的最小值，例如，在 O(logx) 调用中高炉。

---

找到形成负循环所需的边 (u,v) 的最小权重的更有效解决方案是删除该边，从 v 中找到最短路径code> 到 u。

现在，您可以判断边的权重应该是多少以获得权重为 0 的循环，(-d(v,u))，除此之外 - 您有一个正数循环，少 - 负循环。