algorithm - Sedgewick 和 Wayne 的 Bellman ford 基于队列的方法 - 算法，第 4 版

Question

我在学习queue-based Bellman-Ford algorithm 的方法对于来自 Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition 的单源最短路径此链接提供了本书算法的源代码 http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java .

我有两点，一是疑惑，二是代码改进建议。

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) 则检测周期为真，则周期不一定会在恰好发生时发生是真的。所以我认为除数可以是任何足够小的数字，以便我们可以在适当的时间间隔后检查循环。我这样想对吗？

1. 代码改进建议是findNegativeCycle()如果循环发生，方法可用于返回 true。因此。这种情况-

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

可以改成-

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

在代码中，即使 findNegativeCycle() 循环也会继续运行方法找到了一个循环。所以我们可以在循环发生时返回，而不是处理 for 循环的剩余部分。

请分享您对以上两点的看法。提前致谢。

Answer 1

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

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

换句话说，您可以更频繁地检查，但这样您就有性能损失的风险。

1. 再一次，你是对的。当前在构造函数的while 循环中检查是否存在负循环。然而，在最坏的情况下，relax 方法可以通过检查 for 循环中的第一个边缘来检测循环，而不是退出它，而是继续检查其他边缘(max V-2 个)。根据您提出的改进建议，可以节省大量时间。