c++ - 使用 Bellman Ford 检测产品超过阈值的周期

Question

Bellman Ford用于检测图中的负加权循环。我想知道如何使用它来检测 超过 某个阈值的周期。

示例:

               --------->
               ^        |1
       0.5     | <------v
1 -----------> 2 
^             |
|4            |1
|     2       v
4<------------3 

此图有 2 个循环。一个乘积 = 1，另一个乘积 = 4。如果阈值 = 1，算法应输出 true，因为有 1 个乘积 > 1 的循环。

Answer 1

我假设您想检测一个权重超过某个阈值的简单循环(否则，您可以重复任何正权重 >1 个循环足够的次数以超过任何正阈值)。

不幸的是，这个问题是NP-Hard .

Hamiltonian cycle problem 的简单缩减:

给定哈密顿循环问题的实例 G=(V,E)，保持相同的图 G，其中 w(e) = 2 为任何边缘，并将其发送到阈值 2^|V|-1 的问题。
如果有任何环的权重大于2^|V|-1，那么它有多于|V|-1`条边，所以这个环是哈密顿环，如果有是一个哈密顿环，算法会发现有一个权重为2*2*...*2> 2^|V|-1的环。

由于 Hamiltonian Cycle 是 Np-Complete，并且我们发现从它到这个问题的多项式约简，这个问题是 NP-Hard，并且没有已知的多项式解。

---

tl;dr:使用 Bellman Ford 解决这个问题绝非易事，如果可能的话，需要将图修改为原始图大小的指数(假设 P!=NP)