负权重循环算法

栏目: 编程工具 · 发布时间: 6年前

内容简介:翻译自: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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

社交网站的数据挖掘与分析

社交网站的数据挖掘与分析

Matthew A. Russell / 师蓉 / 机械工业出版社 / 2012-2 / 59.00元

Facebook、Twitter和LinkedIn产生了大量宝贵的社交数据,但是你怎样才能找出谁通过社交媒介正在进行联系?他们在讨论些什么?或者他们在哪儿?这本简洁而且具有可操作性的书将揭示如何回答这些问题甚至更多的问题。你将学到如何组合社交网络数据、分析技术,如何通过可视化帮助你找到你一直在社交世界中寻找的内容,以及你闻所未闻的有用信息。 每个独立的章节介绍了在社交网络的不同领域挖掘数据的......一起来看看 《社交网站的数据挖掘与分析》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

随机密码生成器
随机密码生成器

多种字符组合密码