负权环算法

Question

我在思考如何在有向图中寻找负权重环的算法。问题是：我们有一个图G(V,E)，我们需要找到一种有效的算法来查找具有负权重的环。我理解了这份PDF文件中的算法。

简要地说，该算法是通过迭代|V|-1次进行松弛来应用Bellman Ford算法。之后，它检查是否存在可以进一步松弛的边，如果存在负权重环，我们可以通过父指针将其追溯回去，然后一切顺利，我们找到了负权重环。

然而，我想到了另一种算法，只需在图上使用深度优先搜索(DFS)，并跟踪您遍历的距离总和即可。一开始将所有节点标记为白色，当我搜索路径时，将它们标记为灰色，并在完成时将它们标记为黑色，这样我就知道，如果找到一个已访问的节点，并且它是灰色的(在我的路径上)，而不是黑色(已经由深度优先搜索完成)，则表示我找到了一个环。对于我的算法，如果我到达一个已经被访问过的灰色节点，我会检查它的更新值(新距离)，如果比之前低，那么我就知道有一个负权重环并可以追溯回去。

我的算法是否有错？如果有，你能找到反例吗？如果没有，你能帮我证明吗？

谢谢。

- Saher Ahwal

---

为了找到一个负环，像这样的算法必须遍历它。我怀疑在一个大图中，可能存在非常多的循环。在一个完全连接的有N个节点的图中，将从第一个节点开始并依次访问每个其他节点的N！/ N个循环。因此，我认为您的算法必须比Bellman-Ford花费更长的时间，或者在某些图形中错过一些循环。 - mcdowella

你从每个节点开始进行深度优先搜索吗？如果不是，你从哪些节点开始搜索？ - Larry Watanabe

我的深度优先搜索遍历了所有节点，当它卡住时，它会找到另一个入度为0的节点并再次进行深度优先搜索。总体而言，我的DFS应该在O（V + E）时间内运行（线性）。 - Saher Ahwal

Answer 1

Bellman Ford并非总是有效的，问题在于它是一种单源最短路算法，如果从您选择的源无法到达负循环，则会失败。但对Bellman Ford进行一点改变可以帮助解决这个问题，而不是选择源顶点并将其距离初始化为0，我们可以将所有距离初始化为0，然后运行Bellman Ford。 这相当于添加一个额外的顶点s'，它指向原始图中具有0权重边缘的所有顶点。 在图上运行Bellman Ford并找到任何使d [u] + w [u] [v]

DFS无论如何都不起作用，显然它不能耗尽所有可能的循环。 DFS可用于查找图中的循环存在性，但仅此而已。

- shuais

---

能否详细介绍一下追踪回溯（tracking back）？通过追踪回溯找到的循环必须是负循环吗？这是否意味着，如果不满足 d[u] + w[u][v] < d[v]，则前任图中就没有循环？ - hakunami

@hakunami 前驱图每个顶点有一条边。任何具有n个顶点的图都将具有一个环，因此前驱图具有一个环。并且BF算法永远不会产生非负环，因此我们保证可以找到一个负环。 - RussellStewart

Answer 2

一个明显的问题，你正在标记节点。

 A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

假设你走了A->B->D这条路，到达D时ABD都是灰色的。没有找到循环。你回到了A；B和D变成了黑色。你沿着边继续走，因为D已经被标记为黑色，所以没有找到循环。

一般来说，路径数量与图的大小呈指数关系。你必须尝试每条路径，这里没有办法标记节点。如果你单独处理有向图中每个边的方向，我相信你可以标记这些边，但这等同于枚举所有路径。

- dfb

Answer 3

山田木下算法于2003年解决了在有向加权图中使用检测到的循环的最大顶点计数的上限来找到所有负权重循环的问题。

尽管实现具有挑战性。

摘要

给定一个带有权重的有向图，其中边缘与权重相关，不一定是正数，我们关注的问题是查找所有具有负总权重的基本环。在这样的图形中找到所有基本环或检测是否存在负循环的算法已经得到充分探索。然而，似乎还没有探索如何找到所有成本为负的基本循环。我们开发了一种基于“分而治之”范例的算法来解决这个问题，并在一些数值实验中评估其性能。

来源于2002年5月《离散应用数学》118(3):279-291 https://www.researchgate.net/publication/220570430_Finding_all_the_negative_cycles_in_a_directed_graph

- Gewure

Answer 4

我相信有一种方法可以在线性时间内解决这个问题。 在使用深度优先搜索（DFS的运行时间为O（V + E））搜索图时，您可以跟踪从源到当前节点的距离（通过将父节点的距离与连接子节点和父节点的边的权重简单递增）。 然后，每当遇到一个循环（在无向图中通过找到反向边，在有向图中通过找到反向边或前向边来发现循环），您可以减去源节点和循环根节点之间的距离，从源节点到循环中最终节点的距离（根节点是循环开始的节点）。 如果结果为负，则循环必须为负！

- JMS