9

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

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

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

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

谢谢你

4

4 回答 4

17

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 可用于查找图中是否存在循环，但仅此而已。

于 2012-10-21T05:49:31.590 回答
3

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

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

假设你走路径 A->B->D，当你点击 D 时，ABD 是灰色的。没有找到循环。你跳到A；B 和 D 是黑色的。你占据优势，没有找到循环，因为 D 是黑色的。

通常，路径的数量与图的大小成指数关系。您必须尝试每条路径，这里无法标记节点。如果您分别处理有向图中的每个边缘方向，我相信您可以这样做标记边缘，但是，这相当于枚举所有路径。

于 2011-04-05T23:03:29.073 回答
-1

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

于 2013-11-15T21:26:56.510 回答
-1

2003 年的Yamada/Kinoshitas 算法解决了使用检测到的循环的最大顶点数上限在有向加权图中查找所有负加权循环的问题。

但是，实施起来非常具有挑战性。

抽象的

给定一个有向图，其中边与不一定为正的权重相关联，我们关心的是找到所有总权重为负的基本循环的问题。找到所有基本循环或检测（如果存在）这种图中的负循环的算法得到了很好的探索。然而，找到所有具有负成本的基本循环似乎是未探索的。我们开发了一种基于“分而治之”范式的算法，并在一些数值实验中评估其性能。

从 2002 年 5 月开始离散应用数学118(3):279-291 https://www.researchgate.net/publication/220570430_Finding_all_the_negative_cycles_in_a_directed_graph

于 2020-12-28T03:40:18.400 回答