5

我正在研究 从书中算法的源代码获取单一源最短路径的queue-based方法，此链接位于http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java。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)。所以我认为除数可以是任何足够小的数字，以便我们可以在适当的时间间隔后检查周期。我这样想对吗？

  1. 代码改进建议是，findNegativeCycle()如果发生循环，可以使用该方法返回 true。因此。这个条件——

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

可以改成——

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

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

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

4

2 回答 2

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

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

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

  1. 再说一次，你是对的。当前while在构造函数中的循环中检查是否存在负循环。然而，在最坏的情况下，该relax方法可以通过检查循环中的第一个边来检测for循环，而不是退出，它将继续并检查其他边（V-2其中的最大值）。通过您建议的改进，可以节省大量时间。
于 2015-04-23T12:48:41.520 回答
0

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

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 的构造函数中更好地设计，方法是记住每次通过时要放松多少个顶点。我对么？谢谢！

于 2015-08-17T02:14:40.000 回答