内容简介：翻译自：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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
营销三大算法
刘学林、刘逸春、张新春、王颖、余彬晶、刘锦炽、董少灵、沈逸超、王锐睿、孙静若 / 上海交通大学出版社 / 2018-1-31 / 88.00元
未来的营销应该是数字化的，即数字营销。以数据为本，用演算做根，数字营销能够演算生活的方方面面。在数字营销领域，市场的整个投入、产出带来什么东西？企业一定要狠清楚地知道，这是做数字营销的本质。数字营销和企业做生意的本质是一样的，目的都是以投入换取产出。 本书由正和岛数字营销部落编写，基于大量企业的案例与数据，提出了营销三大核心算法与一套全局营销系统，帮助企业CEO与营销人员科学化建立全局营销系......一起来看看 《营销三大算法》 这本书的介绍吧!
