在一个特殊的有向图中找到权重> 0的所有周期

Question

我正在寻找一种算法来查找所有周期的总重量大于零的所有边。我听说这个问题是NP完全的，但因为我想解决这个问题，总是看起来差不多一样，所以我希望有一个更简单的方法。

My图表看起来是这样的：

它始终是所有horizo​​nzally和垂直相邻顶点之间的N * N的顶点和边的sqaure。只有两种可能的权重，黑边-1和绿色+1。

在这个例子中我正在寻找的周期将是：

---

• 7; 12; 17; 18; 19; 14; 13; 8; 7 =>体重：+1
• 7; 12; 13; 8; 7 =>体重：+1
• 7; 8; 7 =>体重：+2
• 18; 23; 24; 19; 18 =>体重：+1
• 7; 12; 17; 18; 23; 24; 19; 14; 13; 8; 7重：=> +2

---

什么是承担这一任务的高效算法？它应该是非常快的，因为我也想为n = 25 => 625个顶点的图做到这一点。

感谢您的帮助！

Answer 1

为什么不使用带有DFS一个基本周期检测，而一些修改，以使其：

• 当你遇到一个节点，如果你已经访问这个相同的节点，你知道你的是循环，以便检查重量是否为正数，如果是这样，只需再次循环以将路径保留在内存中。
• 如果你正在访问的节点已经被看到就在这里停下来。
• 然后递归访问该节点的邻居。

的伪代码可能是这样的：

dfs(node, weight): 
    if state[node] is "in progress" AND weight > 0 
     // This is a cycle we want 
     Keep in memory the path (just go throught the cycle once more) 
    if state[node] is "visited" 
     Stop 

    state[node] = "in progress" 
    For each neighbour 
     dfs(neighbour, weight + edge_weight) 
    state[node] = "visited" 

如果你这样做，对于各开始节点，你应该在大约O（N * M）时得到一个复杂与数N顶点的数量和M的边数量。

希望这会有所帮助！

编辑：忘了更新状态