内容简介：翻译自：https://stackoverflow.com/questions/5534540/negative-weight-cycle-algorithm
我正在考虑在有向图中找到负权重循环的算法.问题是：我们有一个图G(V,E),我们需要找到一个有效的算法来找到负权重的循环. I understand the algorithm in this PDF document
简而言之,该算法通过迭代| V | -1次进行松弛来应用Bellman Ford算法.之后它会检查是否有一条甚至可以放松的边缘,然后存在一个负的重量循环,我们可以通过父指针追溯它,一切顺利,我们发现负重量循环.
然而,我正在考虑另一种在图上使用深度优先搜索(DFS)的算法,通过跟踪到达距离的总和到目前为止,我在开始时将所有节点标记为白色并在我使用时将它们设置为灰色搜索一个路径,并在它们完成时将它们标记为黑色,这样我知道我找到一个循环当且仅当我找到一个被访问的节点并且它是灰色的(在我的路径中),而不是黑色已经完成了深度 – 首先搜索,对于我的算法,如果我到达一个已经访问过的灰色节点,我会检查它的更新内容(新的距离),如果它比以前低,我知道我有一个负重量循环并可以追溯它.
我的算法错了吗？如果是这样,你能找到一个反例吗？如果没有,你能帮我证明一下吗？
谢谢
一个明显的问题,你是标记节点.
A <---> B
| ^
\--\ |
v
-> D (crap ascii art, A connects to D unidirectionally)
假设你选择路径A-> B-> D,当你点击D时,A B D是灰色的.没有找到循环.你弹出A; B和D是黑色的.你走边缘,没有找到周期因为D是黑色的.
通常,路径的数量与图形的大小成指数关系.你必须尝试每条路径,这里没有办法标记节点.如果你分别处理有向图中的每个边方向,我相信你能够做到这一点标记边,但是,这相当于枚举所有路径.
翻译自：https://stackoverflow.com/questions/5534540/negative-weight-cycle-algorithm
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
