内容简介：翻译自：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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
数据结构与算法分析
Mark Allen Weiss / 冯舜玺 / 电子工业出版社 / 2016-8 / 89.00元
本书是数据结构和算法分析的经典教材，书中使用主流的程序设计语言C++作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书把算法分析与C++程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。一起来看看 《数据结构与算法分析》 这本书的介绍吧!
