Bellman ford queue based approach from Sedgewick a

问题:

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

I have two points one is a doubt and other is code improvement suggestion.

1. In above approach following is code for relax method for relaxing distance to 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 this method below condition is used before finding negative cycle.

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

Above they are dividing cost by number of vertices in graph to check for negative cycle. It may be because relaxation is done V-1 times and if relaxation run for Vth time it means it has cycle, where V is number of vertices.

But I think in queue-based approach they are using divisor to check at regular interval if cycle has occurred or not. A cycle can occur before or just after above condition is true. If cycle occurred after above condition is true then algorithm has to wait till next time condition is true to detect cycle, it is not necessary that cycle will occur exactly when if (cost++ % G.V() == 0) is true. So I think divisor can be any number small enough so that we can check for cycle after appropriate time interval. Am I right in thinking that?

2. The code improvement suggestion is that findNegativeCycle() method can be used to return true if cycle has occurred. Thus. this condition-

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

Can be changed to-

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

In code for loop keeps on running even if findNegativeCycle() method has found a cycle. So we can return if cycle has occurred instead of processing rest of for loop.

Please share your thoughts for above 2 points. Thanks in advance.

回答1:

1. You are right. In their online materials, authors explain that they check every Vth call in order to amortize the cost of building the associated edge-weighted digraph and finding the cycle in it:

Accordingly, to implement negativeCycle() BellmanFordSP.java builds an edge-weighted digraph from the edges in edgeTo[] and looks for a cycle in that digraph. To find the cycle, it uses EdgeWeightedDirectedCycle.java, a version of DirectedCycle.java from Section 4.3, adapted to work for edge-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 performance loss.

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

回答2:

Very happy to see the answers by Miljen Mikic. It really helps to understand the algorithm. However, I still have another question. In the text, it says "To complete the implementation, we need to ensure that the algorithm terminates after V passes. One way to achieve this end is to explicitly keep track of the passes." Here, I believe the variable "cost" is the count of the passes, but shouldn't the lines

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

be at least outside of the for loop? Like

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++ % G.V() == 0)
              findNegativeCycle();
      }

Actually even it's outside of the for loop, it's not the best solution, as during each pass, there could be multiple vertices to be relaxed. So it could be designed better in the constructor of BellmanFordSP by remembering how many vertices to be relaxed during each pass. Am I correct? Thanks!