Detecting negative cycles using Bellman Ford Algorithm

Question

I know this is a bit of a reach, but I am following Princeton's course on Algorithm. I am trying to use Bellman Ford algorithm to detect negative cycle in edge weighted directed graph.

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.

The complete code implementation are available at : BellmanFordSP.java and EdgeWeightedDirectedCycle.java. Specifically, I'm stuck at this point :

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

What does this condition signify : cost++ % G.V() == 0. Why are we checking for negative cycles on this specific condition only ?

Answer 1

Usually, the Bellman-Ford algorithm does |V|-1 steps of relaxation. If you want to detect negative cycles, you must run the relaxation one more time. If you still can relax the network one more time, it does have a negative cycle.

That's what this condition is checking, if this is the |V|th time you're calling relax.

Note that not always the relaxed edge is part of the cycle, it may be an edge that is reachable from the cycle.

Answer 2

You can check answer to question I asked on stackoverflow Bellman ford queue based approach from Sedgewick and Wayne - Algorithms, 4th edition

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

This condition is used to detect cycle at regular interval. It is not necessary that cycle will occur at exactly when condition is true. A cycle can occur after this condition becomes true, in which case it has to wait next time till this condition cost++ % G.V() == 0 is true to find cycle. If you use any other number (small number close to number of edges or vertices) as divisor instead of number of vertices algorithm will work. Divisor is just used to check for cycle at regular interval.