Bellman ford queue based approach from Sedgewick and Wayne - Algorithms, 4th edition -

i studying queue-based approach bellman-ford algorithmfor single source shortest path robert sedgewick , kevin wayne - algorithms, 4th edition source code algorithm book present @ link http://algs4.cs.princeton.edu/44sp/bellmanfordsp.java.

i have 2 points 1 doubt , other code improvement suggestion.

1. in above approach following code relax method relaxing distance vertices.

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

in method below condition used before finding negative cycle.

if (cost++ % g.v() == 0){      findnegativecycle(); } 

above dividing cost number of vertices in graph check negative cycle. may because relaxation done v-1 times , if relaxation run vth time means has cycle, v number of vertices.

but think in queue-based approach using divisor check @ regular interval if cycle has occurred or not. cycle can occur before or after above condition true. if cycle occurred after above condition true algorithm has wait till next time condition true detect cycle, not necessary cycle occur when if (cost++ % g.v() == 0) true. think divisor can number small enough can check cycle after appropriate time interval. right in thinking that?

2. the code improvement suggestion findnegativecycle() method can used return true if cycle has occurred. thus. condition-

   if (cost++ % g.v() == 0) { findnegativecycle(); }

can changed to-

if (cost++ % g.v() == 0)     if(findnegativecycle()){         return;     } 

in code loop keeps on running if findnegativecycle() method has found cycle. can return if cycle has occurred instead of processing rest of loop.

please share thoughts above 2 points. in advance.

1. you right. in online materials, authors explain check every vth call in order amortize cost of building associated edge-weighted digraph , finding cycle in it:

accordingly, implement negativecycle() bellmanfordsp.java builds edge-weighted digraph edges in edgeto[] , looks cycle in digraph. find cycle, uses edgeweighteddirectedcycle.java, version of directedcycle.java section 4.3, adapted work edge-weighted digraphs. we amortize cost of check performing check after every vth call relax().

in other words, can check more often, risk performance loss.

2. again, right. existence of negative cycle checked in while loop in constructor. however, in worst case relax method can detect cycle checking first edge in for loop, , instead of exiting continue , check other edges (max v-2 of them). suggested improvement can save significant amount of time.