算法，第4版 - 贝尔曼福特队列根据来自塞奇威克和韦恩的方法 [英] Bellman ford queue based approach from Sedgewick and Wayne - Algorithms, 4th edition

问题描述

我在学习基于队列的办法为 Bellman-Ford算法​​对于单一来源的最短路径罗伯特·塞奇威克和凯文韦恩 - 算法，第4版 来源$ C ​​$ C从书的算法是present这个链接的http：// algs4.cs.princeton.edu/44sp/BellmanFordSP.java 。

我有两个点，一个是怀疑，另一个是code改进建议。

1. 在按照上面的方法是code的放松方法，放松距离顶点。

    的（DirectedEdge E：G.adj（V））{
       INT W = e.to（）;
       如果（distTo [瓦特]≥distTo [V] + e.weight（））{
           distTo [瓦特] = distTo [V] + e.weight（）;
           edgeTo [W] = E;
           如果（！onQueue [瓦特]）{
               queue.enqueue（瓦特）;
               onQueue [W] =真;
           }
       }
       如果（成本+％G.V（）== 0）{
           findNegativeCycle（）;
       }
   }
    

在此方法如下条件寻找负周期之前被使用。

 如果（成本+％G.V（）== 0）{
     findNegativeCycle（）;
}
 

以上它们除以顶点图中的一些费用，以检查负循环。这可能是因为 松弛完成 V-1 次，如果 Vth的的时代，这是有周期的，放松跑，其中V是数的顶点。

但我认为基于队列的方法，他们使用的是除数，以检查在固定时间间隔，如果已经发生或不循环。一个周期可能出现 之前或之后上述条件是真实的。如果上述条件后发生周期为真，那么算法要等到下一次条件 真正的检测周期，它会发生周期正好，如果时，是没有必要的（成本+％GV（）== 0）是真实的。所以我觉得除数可以是任何数量足够小，这样我们就可以经过适当的时间间隔检查周期。 我是正确的思维是什么？

<醇开始=2>

在code改良效果的建议在上述计划Bellman-Ford算法​​我是从 findNegativeCycle（）方法，我们就可以返回true 如果周期已经发生，然后这conditon -

如果（成本+％G.V（）== 0）{     findNegativeCycle（）; }

可改为 -

 如果（成本+％G.V（）== 0）
    如果（findNegativeCycle（））{
        返回;
    }
 

在code for循环继续运行，即使 findNegativeCycle（）方法找到了一个循环。因此，我们可以返回，如果周期发生，而不是为环路进行处理，其余部分。

请分享你的想法上面2点。 先谢谢了。

解决方案

1. 您是对的。在他们网上资料中，作者解释说，他们检查每一个Vth的电话，以摊销成本建设相关的边加权有向图，并找到循环是：

  

因此​​，为了实现negativeCycle（）BellmanFordSP.java构建一个   从edgeTo []边边加权有向图，并期待为一周期   在有向图。要查找周期，它使用   EdgeWeightedDirectedCycle.java，从版本DirectedCycle.java的   第4.3节，适应工作边加权有向图。 我们摊销   此次检查的只有每Vth时后进行此项检查的费用   呼吁放松（）

在换句话说，你可以检查次数多，但你冒险的性能损失。

<醇开始=2>

同样，你是对的。负周期的存在是否被选中的，而回路的构造。然而，在最坏的情况下，放松方法可以通过检查为循环第一边缘检测的周期，而不是中退出，将继续检查其他边缘（最大值 V-2 其中）。有了您的建议的改进，可以节省显著的时间。

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 improvment suggestion in above program for Bellman-Ford algorithm I have is from findNegativeCycle() method we can return true if cycle has occured and then this conditon-

   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. 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.

这篇关于算法，第4版 - 贝尔曼福特队列根据来自塞奇威克和韦恩的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！