我在学习基于队列的办法为 Bellman-Ford算法对于单一来源的最短路径罗伯特·塞奇威克和凯文韦恩 - 算法,第4版 来源$ C $ C从书的算法是present这个链接的http:// algs4.cs.princeton.edu/44sp/BellmanFordSP.java 。
我有两个点,一个是怀疑,另一个是code改进建议。
在按照上面的方法是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)是真实的。所以我觉得除数可以是任何数量足够小,这样我们就可以经过适当的时间间隔检查周期。 我是正确的思维是什么?
在code改良效果的建议在上述计划Bellman-Ford算法我是从 findNegativeCycle()方法,我们就可以返回true 如果周期已经发生,然后这conditon -
如果(成本+%G.V()== 0){ findNegativeCycle(); }
可改为 -
如果(成本+%G.V()== 0) 如果(findNegativeCycle()){ 返回; }在code for循环继续运行,即使 findNegativeCycle()方法找到了一个循环。因此,我们可以返回,如果周期发生,而不是为环路进行处理,其余部分。
请分享你的想法上面2点。 先谢谢了。
解决方案因此,为了实现negativeCycle()BellmanFordSP.java构建一个 从edgeTo []边边加权有向图,并期待为一周期 在有向图。要查找周期,它使用 EdgeWeightedDirectedCycle.java,从版本DirectedCycle.java的 第4.3节,适应工作边加权有向图。 我们摊销 此次检查的只有每Vth时后进行此项检查的费用 呼吁放松()
在换句话说,你可以检查次数多,但你冒险的性能损失。
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 algs4.cs.princeton.edu/44sp/BellmanFordSP.java.
I have two points one is a doubt and other is code improvement suggestion.
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?
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.
解决方案
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.
更多推荐
算法,第4版
发布评论