负重量循环算法

我正在考虑在有向图中找到负重量循环的算法。问题是：我们有一个图G（V，E），我们需要找到一个有效的算法来找到负权重的循环。 I understand the algorithm in this PDF document 负重量循环算法

简而言之，该算法通过迭代| V | -1次来应用贝尔曼福特算法来做放松。之后，它检查是否存在可以更放松的边缘，然后存在负的权重循环，并且可以通过父指针追踪它，并且一切都很顺利，我们会发现一个负的权重循环。

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

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

谢谢你

来源

2011-04-04 Saher Ahwal

为了找到一个-ve循环，像这样的算法必须遍历它。我怀疑，在一张大图中，有很多可能的周期。在具有N个节点的完全连通图中，将有第N个/ N个周期从第一个节点开始并依次访问每个其他节点。所以我认为你的算法要么比Bellman-Ford要花费更长的时间，要么在某些图表中错过一些周期。 – mcdowella 2011-04-04 04:32:20

你是否从每个节点做dfs？如果不是，你开始搜索什么节点？ – 2011-04-04 04:34:03

我的dfs遍历了所有的节点，当它被卡住时，它找到另一个0度入度的节点，并再次执行dfs。总的来说，我的DFS应该运行在O（V + E）时间（线性） – 2011-04-04 04:35:35

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

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

假设你采取路径A-> B-> D，当你击中D时，A B D是灰色的。没有找到循环。你弹出到A; B和D是黑色的。你走边缘，没有周期被发现，因为D是黑色的。

通常，路径的数量是指数图的大小。你必须尝试每条路径，这里没有办法标记节点。如果你分别用有向图处理每个边的方向，我相信你可以做到这一点标记边，但是，这相当于枚举所有路径。

来源

2011-04-05 23:03:29 dfb

贝尔曼福特并不总是工作，问题是它的一个单一来源最短路径算法，如果负面循环无法从您选择的来源到达，它会失败。然而，对贝尔曼福特稍作改动可能会有所帮助，而不是选择源顶点并将其距离初始化为0，我们可以将所有距离初始化为0，然后运行Bellman Ford。这相当于增加了一个额外的顶点s'，它指向原始图中0加权边的所有顶点。一旦Bellman Ford在图上运行，并且我们发现任何使得d [u] + w [u] [v]的顶点u和边（u，v），我们知道必须存在负循环对你来说，在前辈图中跟踪你，我们会找到这个循环。

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

来源

2012-10-21 05:49:31 shuais

你能告诉更多关于跟踪回来吗？通过回溯发现的周期必须是负周期？剂量它的意思，如果没有满足d [u] + w [u] [v] hakunami 2014-03-08 08:40:01

@hakunami前趋图对每个顶点都有一条边。任何有n个顶点的图都有一个循环，所以前驱图有一个循环。 BF永远不会产生非负周期，所以我们保证找到一个负周期。 – RussellStewart 2014-04-29 03:11:28

-1

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

来源

2013-11-15 21:26:56 JMS

负重量循环算法

回答

相关问题