我正在研究一个有向图的项目，其中边的权重都取决于一个变量x。
我试图找到x的最小值，这样我的图就不包含任何正权重的电路。
我的问题是-这可能很愚蠢，但我不知道怎么做-：
如何使用改良的贝尔曼福特来检查是否存在正极电路而不是负极电路？
谢谢。
最佳答案
我怎么能用改装过的贝尔曼福特来检查
用正极电路代替负极电路？
将所有权重更改为负值：
w'(u,v) = -w(u,v)
然后简单地运行常规的BF。
可以对该值
x运行二进制搜索，以找到负循环所需的最小值，例如在bf的O(logx)调用中。找到一个负循环所需的边的最小权重的一个更有效的解决方案是移除该边，找到从
(u,v)到v的最短路径。现在，你可以知道边缘的权重应该是多少，得到一个权重为0的循环，（
u），除此之外的任何东西-你有一个正循环，较少-负循环。