内容简介：翻译自：https://stackoverflow.com/questions/5534540/negative-weight-cycle-algorithm
简而言之,该算法通过迭代| 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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
架构真经
马丁L. 阿伯特（Martin L. Abbott）、迈克尔T.费舍尔（Michael T. Fisher） / 机械工业出版社 / 2017-4 / 79
前言 感谢你对本书第2版感兴趣！作为一本入门、进修和轻量级的参考手册，本书旨在帮助工程师、架构师和管理者研发及维护可扩展的互联网产品。本书给出了一系列规则，每个规则围绕着不同的主题展开讨论。大部分的规则聚焦在技术上，少数规则涉及一些关键的思维或流程问题，每个规则对构建可扩展的产品都是至关重要的。这些规则在深度和焦点上都有所不同。有些规则是高级的，例如定义一个可以应用于几乎任何可扩展性问题的模......一起来看看 《架构真经》 这本书的介绍吧!
