1

I am working on a project with directed graphs where the weight of the edges all depend on a variable x. I'm trying to find the minimum value of x such that my graph does not contain any circuit of positive weight.

My question is -and it is probably pretty stupid but I don't see how- : How can I use a modified Bellman-Ford to check for the presence of positive circuits instead of negative circuits ?

Thanks.

4

2 回答 2

0

如何使用修改后的 Bellman-Ford 检查是否存在正电路而不是负电路？

将所有权重更改为负值：

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

然后简单地运行常规BF。

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

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

现在，您可以告诉边缘的权重应该是什么以获得权重为 0 的循环，( -d(v,u))，除此之外 - 你有一个正循环，更少 - 负循环。

于 2015-07-09T13:04:18.147 回答
0

如果您想找到最短路径并且不想使用负边缘，则可以使用与 Bellman-Ford 几乎相似的 Dijkstra 算法。

但是，如果您只想访问权重可能较低的边，您可以查看“Prim 算法”或“Kruskall 算法”，它们用于查找图形的“最小生成树（MST）”。

Dijkstra 算法

Prim 算法

克鲁斯卡尔算法

于 2015-07-09T13:14:34.780 回答