logo标签列表

列出有向图中的所有负环

c#javaalgorithmgraph-algorithm
5

对于一个带有负权值的有向图 G(V,E)，我搜索了一些类似的主题，似乎Bellman-Ford算法可以检测负环。但是一旦发现负环，它就会停止，那么在这种情况下我们如何列出所有负环呢？

根据Eric Lippert的建议，我尝试从图中删除一旦找到的负环，但我感觉这不正确，为什么？因为在删除循环后，图形会发生变化，并且旧图中可能存在额外的非负循环，但在新图中不会被发现。请问有人能帮我澄清这个问题吗？

这可以在Java或C#中实现（我更喜欢C#）。

谢谢

抱歉，我正在修改它，但你比我更快了。 - ikel
找到一个负环。删除它。现在再次搜索。重复此过程，直到您无法找到负环为止。现在，您已经计算了负环的数量。 - Eric Lippert
但那只追踪计数，对吧？我需要完整的路径。 - ikel
什么是负环？ - Jens Schauder
1
在有向图中，边权之和为负值的循环 - ikel
显示剩余2条评论
1个回答
1

嗯，你肯定不能高效地找到它们：考虑完全图上的n个顶点，每条边的权重为负-1。在这个图中有指数级数量的负权重环，因此仅列出它们就需要指数时间！

如果这并不阻止你，你最好应用任何旧的查找循环算法，例如这个问题中的算法，以找到所有循环，然后只丢弃那些带有非负权重的循环。

我的理解是，如果我们尝试找到图中的每个循环，那么它将是指数级别的数字，但是如果我们指出起始节点，那么循环的数量将是有限的，对吗？ - ikel
并不显著。假设您有一个完整的图形，并选择一个特定的节点作为起点。考虑通过此节点的长度为n的循环：显然有(n-1)!条长度为n-1的简单路径从该节点出发，我们只需添加从路径结束到原点的边缘以形成一个循环。因此，通过原点存在(n-1)!个大小为n的循环，这是指数数量。 - Andy Jones
我能想到的唯一打败组合爆炸的方法是要么考虑一个非常受限制的循环集（比如所有长度小于固定长度的循环），要么限制自己只在几乎类似树形的图中进行。编辑：你实际上想要所有负权重循环的列表干什么？如果你能提供一些上下文，可能会有捷径。 - Andy Jones
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接