algorithm - 负权重循环算法

Question

我在想在有向图中寻找负权环的算法。问题是:我们有一个图 G(V,E)，我们需要找到一种有效的算法来找到负权重的循环。 I understand the algorithm in this PDF document

简而言之，该算法通过迭代 |V|-1 次进行松弛来应用 Bellman Ford 算法。之后它检查是否有一条边可以进一步放松，然后存在一个负权重循环，我们可以通过父指针追溯它，一切顺利，我们找到了一个负权重循环。

但是，我正在考虑另一种算法，即通过跟踪到目前为止你走过的距离的总和，在图表上使用深度优先搜索 (DFS)，我在开始时将所有节点标记为白色，然后将它们设为灰色当我搜索路径时，当它们完成时将它们标记为黑色，这样我就知道当且仅当我找到一个访问过的节点并且它是灰色的(在我的路径中)而不是已经完成的黑色时我找到了一个循环通过深度优先搜索，对于我的算法，如果我到达一个已经访问过的灰色节点，我会检查它的更新是什么(新距离)，如果它比以前低，我知道我有一个负的重量循环，并且可以追溯。

我的算法错了吗？如果是这样，你能找到一个反例吗？如果不是，你能帮我证明一下吗？

谢谢

Answer 1

Bellman Ford 并不总是有效，问题在于它的单源最短路径 算法，如果从您选择的源无法到达负循环，它就会失败。然而，对 Bellman Ford 的一点改变可能会有所帮助，而不是选择一个源顶点并将其距离初始化为 0，我们可以将所有距离初始化为 0，然后运行 ​​Bellman Ford。这相当于增加了一个额外的顶点s'，它指向原始图中所有权重为0的边的顶点。一旦 Bellman Ford 在图上运行，我们发现任何使 d[u] + w[u][v] < d[v] 的顶点 u 和边 (u,v)，我们知道必须有一个负循环导致到 u，在前导图中从 u 回溯，我们将找到循环。

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