基于Bellman ford队列的方法来自Sedgewick和Wayne - Algorithms,第4版

Question

我正在研究 这个链接http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java上的来自书籍的算法源代码的单源最短路径的queue-based方法.Bellman-Ford algorithmRobert Sedgewick and Kevin Wayne - Algorithms, 4th edition

我有两点是一个疑问,另一个是代码改进建议.

1. 在上述方法中,以下是用于放松到顶点的距离的松弛方法的代码.

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

在该方法中,在找到负循环之前使用以下条件.

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

以上他们将成本除以vertices图表中的数量来检查negative cycle.这可能是因为放松是在V-1时间上进行的,并且如果放松Vth时间运行则意味着它具有周期,其中V是顶点的数量.

但我认为在基于队列的方法中,他们使用除数来定期检查周期是否已经发生.在上述条件成立之前或之后,可以发生循环.如果在上述条件为真后发生循环,则算法必须等到下一次条件为真检测循环时,如果(cost++ % G.V() == 0)为真,则不必完全发生循环.所以我认为除数可以是足够小的任何数,以便我们可以在适当的时间间隔后检查周期.我是否正确地想到了这一点？

2. 代码改进建议是findNegativeCycle()如果循环已经发生,该方法可用于返回true.从而.这种情况 -

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

可以改为 -

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

在代码中循环继续运行,即使findNegativeCycle()方法已经找到一个循环.所以我们可以在循环发生时返回,而不是处理for循环的其余部分.

请分享您对2分以上的想法.提前致谢.

Answer 1

1. 你是对的。在他们的在线材料中，作者解释说，他们检查每个 Vth 调用，以便分摊构建相关边加权有向图并查找其中循环的成本：

因此，为了实现 negativeCycle()，BellmanFordSP.java 从 edgeTo[] 中的边构建边加权有向图，并在该有向图中查找循环。为了找到循环，它使用 EdgeWeightedDirectedCycle.java，这是第 4.3 节中的 DirectedCycle.java 的一个版本，适用于边加权有向图。我们通过仅在每次 Vth 调用relax() 后执行此检查来摊销此检查的成本。

换句话说，您可以更频繁地检查，但您会面临性能损失的风险。

2. 再说一遍，你是对的。当前在构造函数的循环中检查是否存在负循环while。然而，在最坏的情况下，该relax方法可以通过检查循环中的第一个边沿来检测循环for，并且不会退出，而是继续检查其他边沿（最多V-2）。根据您建议的改进，可以节省大量时间。