使用贝尔曼福特算法检测负循环

Question

我知道这有点难以捉摸，但我正在学习普林斯顿大学的算法课程。我正在尝试使用贝尔曼福特算法来检测边缘加权有向图中的负循环。

There is a negative cycle reachable from the source if and only if the queue is 
nonempty after the Vth pass through all the edges. Moreover, the subgraph of 
edges in our edgeTo[] array must contain a negative cycle.

完整的代码实现可在以下位置获得：BellmanFordSP.java和EdgeWeightedDirectedCycle.java。具体来说，我被困在这一点上：

public class BellmanFordSP 
{
    private double[] distTo;   // distTo[v] = distance  of shortest s->v path
    private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
    private boolean[] onQueue;     // onQueue[v] = is v currently on the queue?
    private Queue<Integer> queue;  // queue of vertices to relax
    private int cost;              // number of calls to relax()
    private Iterable<DirectedEdge> cycle;// negative cycle (or null if no such cycle)
    // Computes a shortest paths tree from s to every other vertex
    public BellmanFordSP(EdgeWeightedDigraph G, int s) 
    {
        distTo  = new double[G.V()];
        edgeTo  = new DirectedEdge[G.V()];
        onQueue = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        // Bellman-Ford algorithm
        queue = new Queue<Integer>();
        queue.enqueue(s);
        onQueue[s] = true;
        while (!queue.isEmpty() && !hasNegativeCycle()) 
        {
            int v = queue.dequeue();
            onQueue[v] = false;
            relax(G, v);
        }
    }
    // relax vertex v and put other endpoints on queue if changed
    // G.V() gives number of vertices in G
    // G.adj(v) returns an Iterable of edges emanating from vertex v.
    private void relax(EdgeWeightedDigraph G, int v) 
    {
        for (DirectedEdge e : G.adj(v)) 
        {
            int w = e.to();
            if (distTo[w] > distTo[v] + e.weight()) 
            {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                if (!onQueue[w]) 
                {
                    queue.enqueue(w);
                    onQueue[w] = true;
                }
            }
            if (cost++ % G.V() == 0)    // <-- what does this check do ?
                findNegativeCycle();
        }
    }
    // Is there a negative cycle reachable from the source vertex s?
    public boolean hasNegativeCycle() 
    {
        return cycle != null;
    }

    // Returns a negative cycle reachable from the source vertex s
    public Iterable<DirectedEdge> negativeCycle() 
    {
        return cycle;
    }
    // by finding a cycle in predecessor graph
    private void findNegativeCycle() 
    {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++)
            if (edgeTo[v] != null)
                spt.addEdge(edgeTo[v]);
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
        cycle = finder.cycle();
    }

这个条件意味着什么：cost++ % G.V() == 0。为什么我们只检查这种特定条件下的负循环？

Answer 1

通常，贝尔曼-福特算法确实 |V|-1 放松步骤。如果要检测负周期，则必须再次运行松弛。如果您仍然可以再次放松网络，它确实有一个负循环。

这就是此条件正在检查的内容，如果这是 |V|th时间你叫放松。

请注意，并非松弛边总是循环的一部分，它可能是可从循环到达的边。

Answer 2

您可以查看我在堆栈溢出贝尔曼福特基于队列的方法上提出的问题的答案，来自塞奇威克和韦恩 - 算法，第 4 版

if (cost++ % G.V() == 0)    
    findNegativeCycle();

这种情况用于定期检测周期。循环不一定恰好在条件为真时发生。在此条件变为 true 后，可能会发生循环，在这种情况下，它必须等待下次，直到此条件cost++ % G.V() == 0为真才能找到循环。如果您使用任何其他数字（接近边或顶点数的小数）作为除数而不是顶点数算法将起作用。除数仅用于定期检查周期。