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

Question

我正在研究 queue-based Bellman-Ford algorithm 的方法，以获得来自 Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition 的单源最短路径书中算法的源代码出现在 link http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java.

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

在上面的方法中，下面是放松顶点距离的放松方法的代码。

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) 为真，则检测周期为真，则不必恰好在 (cost++ % G.V() == 0) 为真时发生周期。所以我认为除数可以是任何足够小的数字，以便我们可以在适当的时间间隔后检查循环。我的想法对吗？

代码改进建议是findNegativeCycle()方法可用于return true if cycle occurred。因此。这种情况-

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

可以改成-

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

在代码中，即使 findNegativeCycle() 方法找到了一个循环，循环也会继续运行ning。所以我们可以 return if cycle has occurred 而不是处理剩余的 for 循环。

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

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

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

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

Answer 2

很高兴看到 Miljen Mikic 的回答。它确实有助于理解算法。不过，我还有一个问题。在文本中，它说“要完成实现，我们需要确保算法终止 V通过后。实现这一目标的一种方法是明确跟踪通行证。”在这里，我相信变量 "cost" 是通行证的计数，但行

不应该

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

至少在 for 循环之外？喜欢

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

实际上，即使它在 for 循环之外，也不是最好的解决方案，因为在每次遍历期间，可能会有多个顶点要松弛。因此，在 BellmanFordSP 的构造函数中可以通过记住每次传递期间要松弛的顶点数来更好地设计它。我对么？谢谢！

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

Bellman ford queue based approach from Sedgewick and Wayne - Algorithms, 4th edition

algorithm

shortest-path

graph-algorithm

bellman-ford