贝尔曼福特被用于检测在图形负加权循环。 我想知道我可以用它来检测超过一定的阈值，而不是循环。
例：
--------->
^ |1
0.5 | <------v
1 -----------> 2
^ |
|4 |1
| 2 v
4<------------3
该曲线图中有2个循环。 一个与产品= 1和其它与产品= 4，如果阈值= 1，该算法应输出真，由于存在1个周期与产品> 1。
我假设你想检测具有权重的简单循环超过某个阈值（否则，你可以重复任何积极的重量> 1循环足够的时间超过任何积极的阈值）。
不幸的是，这个问题是NP难 。
从一个简单的还原哈密顿圈的问题 ：
给定一个实例G=(V,E)哈密顿周期的问题，保持相同的曲线图G ，用w(e) = 2为任何边缘，并将其与阈值发送到所述问题2^|V|-1 。
如果没有与重量比更大的任何周期2^|V|-1, then it has more than | V | -1`边缘，所以这个周期是哈密尔顿，如果有一个汉密尔顿的周期，算法会发现有是重量2 * 2 * ... * 2> 2 ^的周期| V | -1。
由于Hamilton回路是NP完全的，我们发现多项式归约从中这个问题，这个问题是NP难，而且没有已知的多项式解决的办法。
TL; DR：使用贝尔曼福特来解决这个问题，是远离琐碎，和如果可能的话，将需要修改的图表是在原始图形的尺寸指数（！假设P = NP）
部分解决问题
该解决方案工作时，每当所述阈值等于1。
TL;边缘的博士变化的权重，通过应用对数，并使用弗洛伊德-Warshal检测负周期，这将发生，如果一个周期的原始权重的乘积大于1。
长的答案 。 弗洛伊德-Warshal可用于APSP，以及检测在图形负循环 。 为了使这个问题的一个问题，是解决包括寻找负。 周期，做到以下几点：
log(weight of edge) * (-1) 该值将成为积极的，如果原来的值大于1，或者换句话说小：它是阴性的所有值大于1。
由于log(m * n) = log(m) * log(n)我们不必再相乘得到的结果，而只是添加日志。
因此，如果算法发现了一个不良的循环，我们就可以知道，从原来的周期的产品它单曲边缘大于1。
