用Bellman-Ford算法检测负循环

Question

我知道这有点难，但我正在学习普林斯顿大学的算法课程。我尝试使用Bellman-Ford算法来检测边加权有向图中的负圈。

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();
    }

这个条件表示什么：开销%G. V（）==0。为什么我们只在这个特定的条件下检查负循环？

Answer 1

您可以查看我在Sedgewick and Wayne-Algorithms第四版中关于stackoverflow Bellman ford基于队列的方法的问题的答案

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

此条件用于定期检测循环。循环不必在条件为真时发生。此条件变为真后可能会出现一个周期，在这种情况下，必须等到下次此条件成本%G.V（）==0为真后才能找到周期。如果使用任何其他数字（接近边数或顶点数的小数字）作为除数而不是顶点数，则该算法将起作用。除数只是用来检查定期的循环。

Answer 2

通常，Bellman-Ford算法执行| V |-1个松弛步骤。如果要检测负循环，必须再次运行松弛。如果你仍然可以放松网络一次，它确实有一个消极的循环。

这就是这个条件所要检查的，如果这是你第| V |次打电话给放松。

注意，松弛边缘并不总是循环的一部分，它可以是可从循环到达的边缘。