Bellman Ford-based Queues from Sedgewick and Wayne - Algorithms, 4th Edition

Question

I studied the queue-based approach for the Bellman-Ford algorithm for the shortest path with one source from Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition source code for the algorithm from the book is available at this link http://algs4.cs.princeton.edu/ 44sp / BellmanFordSP.java .

I have two points, one of which is doubt, and the other is a suggestion for improving the code.

• In the above approach, the following code for the attenuation method is to relax the distance to the peaks.

   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++ % GV() == 0){ findNegativeCycle(); } } 

In this method, the condition below is used until a negative cycle is found.

 if (cost++ % GV() == 0){ findNegativeCycle(); } 

Above, they divide the cost by the number of vertices in the graph to check the negative cycle . Maybe because relaxation is performed V-1 times, and if relaxation is performed for Vth time, this means that it has a cycle, where V is the number of vertices.

But I think that in the queue-based approach, they use a divisor to check at a regular interval if the cycle has occurred or not. A cycle may occur before or immediately after the condition is higher. If the cycle occurred after the above condition is true, then the algorithm must wait until the next time condition true to detect the cycle, there is no need for the cycle to happen exactly if (cost++ % GV() == 0) - true. Therefore, I think that divisor can be any number small enough so that we can check the loop after the corresponding time interval. Am I right in thinking about this?

2. The recommendation for code improvement is that the findNegativeCycle() method can be used to return true if a loop has occurred. Thus. this condition -

   if (cost++ % GV() == 0) { findNegativeCycle(); }

Can be changed to -

 if (cost++ % GV() == 0) if(findNegativeCycle()){ return; } 

In the for loop, the loop continues to work, even if the findNegativeCycle() method found the loop. Thus, we can return if the cycle occurred instead of processing the rest of the cycle.

Share your thoughts above 2 points. Thanks in advance.

Answer 1

• You're right. In their online materials, the authors explain that they check every Vth call in order to amortize the cost of constructing a diffractor connected with the edge and searching for a cycle in it:

Accordingly, to implement negativeCycle (), BellmanFordSP.java creates a kraft-weighted digraph from the edges in edgeTo [] and looks for a loop in that digraph. To find this loop, it uses EdgeWeightedDirectedCycle.java, a version of DirectedCycle.java from Section 4.3, adapted for working with kraft-weighted digraphs. We amortize the cost of this check by performing this check only after every Vth call to relax () .

In other words, you can check more often, but then you risk losing productivity.

2. Again, you are right. The existence of a negative loop is currently checked in the while in the constructor. However, in the worst case, the relax method can detect the loop by checking the first edge of the for loop, and instead of exiting, continue and check the other edges (max V-2 of them). With the proposed improvement, which can save a significant amount of time.

Answer 2

I am very glad to see the answers of Milen Mikic. It really helps to understand the algorithm. However, I still have another question. The text says: "To complete the implementation, we need to make sure that the algorithm is completed after passing V. One of the ways to achieve this goal is to explicitly track the passes." Here I believe that the variable "cost" is the number of passes, but there should be no rows

 if (cost++ % GV() == 0) findNegativeCycle(); 

be at least outside the for loop? how

 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 (!onQ[w]) { q.enqueue(w); onQ[w] = true; } } } if (cost++ % GV() == 0) findNegativeCycle(); } 

In fact, even this is outside the for loop, this is not the best solution, since during each pass there may be several edges that need to be relaxed. Therefore, it could be better constructed in the BellmanFordSP constructor, remembering how many vertices need to be relaxed during each pass. I'm right? Thanks!