负权重循环算法
我正在考虑在有向图中找到负权循环的算法。问题是：我们有一个图 G(V,E)，我们需要找到一种有效的算法来找到负权重的环。 我了解此 PDF 文档中的算法
简而言之，算法正在应用贝尔曼福特算法，通过迭代 |V|-1 次进行松弛。然后它检查是否有一条边可以更放松，然后存在负权重循环，我们可以通过父指针追溯到它，一切顺利，我们发现一个负权重循环。
然而，我正在考虑另一种算法，即通过跟踪到目前为止所经过的距离的总和，在图上使用深度优先搜索（DFS），我在开始时将所有节点标记为白色，并在开始时将它们设为灰色。搜索路径，并在完成后将它们标记为黑色，这样我知道当且仅当我找到一个被访问的节点并且它是灰色的（在我的路径中），而不是已经由深度完成的黑色时，我才找到一个循环-第一次搜索，对于我的算法来说，如果我到达一个已经访问过的灰色节点，我会检查它的更新是什么（新距离），如果它比以前低，我知道我有一个负权重循环并可追溯。
我的算法有问题吗？如果是的话，你能找到一个反例吗？如果不是你能帮我证明一下吗？
谢谢
I was thinking about the algorithm of finding a negative weight cycle in a directed graph. The Problem is: we have a graph G(V,E), we need to find an efficient algorithm to find a cycle with negative weight. I understand the algorithm in this PDF document
Briefly, the algorithm is applying Bellman Ford algorithm by iterating |V|-1 times doing relaxations. Afterwards it checks if there is an edge that can be even relaxed more, then a negative weight cycle exists and we can trace it back by parent pointers and everything goes well, we find a negative weight cycle.
However, I was thinking of another algorithm of just using depth-first search (DFS) on the graph by keeping track of the sum so far of the distances you traversed, I mark all nodes white at the beginning and make them grey when I am searching a path, and mark them black when they are finished, that way I know that I find a cycle if and only if I find a visited node and it is grey (in my path) , not black which was already finished by the Depth-First search, and so for my algorithm, if I reach a grey node that has already been visited, I check what would it's update be (the new distance) and if it is lower than before, I know that I have a negative weight cycle and can trace it back.
Is my algorithm wrong? If so, can you find a counterexample ? If not can you help me prove it?
Thank You
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
一个明确的问题是，您正在标记节点。
假设你选择路径A->B->D，当你点击D时，ABD是灰色的。没有找到循环。你弹出到A； B和D是黑色的。你取边，没有找到环，因为 D 是黑的。
一般来说，路径的数量与图的大小成指数关系。您必须尝试每条路径，这里无法标记节点。如果您单独处理有向图中的每个边缘方向，我相信您能够标记边缘，但是，这相当于枚举所有路径。
One clear problem, you're marking the nodes.
Suppose you take path A->B->D, A B D are grey when you hit D. No cycle is found. You pop out to A; B and D are black. You take the edge, no cycle is found because D is black.
In general, the number of paths is exponential to the size of the graph. You'd have to try every path, there's no way to mark nodes here. If you treated each edge direction in directed graph separately, I believe you'd be able to do this marking the edges, however, this is equivalent to enumerating all paths.
2003 年的 Yamada/Kinoshitas 算法解决了使用最大顶点数上限在有向加权图中查找所有负加权循环的问题检测到的周期。
但实施起来相当具有挑战性。
2002 年 5 月起离散应用数学 118(3):279-291
Yamada/Kinoshitas Algorithm from 2003 solves the problem of finding all negative weighted cycles in a directed weighted graph using upper limits on the max-vertices count of a detected cycle.
It is quite challenging to implement, though.
From May 2002 Discrete Applied Mathematics 118(3):279-291
https://www.researchgate.net/publication/220570430_Finding_all_the_negative_cycles_in_a_directed_graph
我相信有一种方法可以在线性时间内解决这个问题。
当使用深度优先搜索（DFS 的运行时间为 O(V+E)）搜索图时，您可以跟踪从源到当前节点的距离（通过简单地用父节点的权重来增加父节点的距离）将子节点连接到父节点的边）。
然后，每当遇到环路（通过在无向图中查找后边或有向图中的后边或前边发现环路）时，您可以减去源之间的距离循环中的源节点和最终节点之间的距离（根节点是循环开始的节点）。
如果结果为负，则循环一定为负！
I believe there is a way to solve this in linear time.
While searching the graph with depth-first-search (DFS has a runtime of O(V+E)), you can keep track of the distance from the source to the current node (by simply incrementing the parent's distance with the weight of the edge connecting the child node to the parent).
Then, whenever you encounter a cycle (cycles are discovered through finding a back edge in an undirected graph or either a back edge or a forward edge in a directed graph), you can subtract the distance between the source node and the root node of the cycle from the distance between the source node and the final node in the cycle (the root node being the node where the cycle began).
If the result is negative, the cycle must be negative!
贝尔曼福特并不总是有效，问题是它的单源最短路径算法，如果从您选择的源无法到达负循环，它就会失败。然而，对 Bellman Ford 进行一点更改可能会有所帮助，我们可以将所有距离初始化为 0，然后运行 Bellman Ford，而不是选择源顶点并将其距离初始化为 0。这相当于添加一个额外的顶点s'，它指向原图中所有边权重为0的顶点。一旦 Bellman Ford 在图上运行，我们就找到了任何使 d[u] + w[u][v] < 的顶点 u 和边 (u,v)。 d[v]，我们知道一定有一个负循环通向u，从前驱图中的u追溯，我们就会找到循环。
DFS 不会以任何方式工作，它显然无法耗尽所有可能的循环。 DFS 可用于查找图中是否存在环，但仅此而已。
Bellman Ford doesn't always work, the problem is its a single source shortest path algorithm, if the negative loop is not reachable from the source you pick, it fails. However a little change to Bellman Ford could help, instead of selecting a source vertex and initialise its distance to 0, we can initialise all the distance to 0 and then run Bellman Ford. This is equivalent to add a extra vertex s' which points to all the vertexes in the original graph with 0 weight edge. Once Bellman Ford is run on the graph and we found any vertex u and edge (u,v) that make d[u] + w[u][v] < d[v], we know there must be a negative cycle leading to u, tracking back from u in the predecessor graph and we'll find the cycle.
DFS is not gonna work in any way, it's obviously not able to exhaust all possible cycles. DFS can be used to find the presence of cycle in graph, but no more.