负权重循环算法

Question

我正在考虑在有向图中找到负权重循环的算法.问题是:我们有一个图G(V,E),我们需要找到一个有效的算法来找到负权重的循环.我理解本PDF文档中的算法

简而言之,该算法通过迭代| V | -1次进行松弛来应用Bellman Ford算法.之后它会检查是否有一条甚至可以放松的边缘,然后存在一个负的重量循环,我们可以通过父指针追溯它,一切顺利,我们发现负重量循环.

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

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

谢谢

Answer 1

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

DFS不会以任何方式工作,显然无法耗尽所有可能的周期.DFS可用于在图中查找循环的存在,但不能再使用.

Answer 2

一个明确的问题是，您正在标记节点。

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

假设你选择路径A->B->D，当你点击D时，ABD是灰色的。没有找到循环。你弹出到A；B和D是黑色的。你取边，没有找到环，因为 D 是黑色的。

一般来说，路径的数量与图的大小成指数关系。您必须尝试每条路径，这里无法标记节点。如果您单独处理有向图中的每个边缘方向，我相信您能够标记边缘，但是，这相当于枚举所有路径。