0

我对 Bellman-Ford 进行了轻微的修改，使它只做“有用的”放松。也就是说，更新了意味着 d(v) 的松弛。

define Relax(u, v):
 if d(v) > d(u) + w(u,v)         //w(u,v) = weight of edge u->v
    d(v) = d(u) + w(u,v)


INIT // our usual initialization.
Queue Q
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q not empty)
{
  u ← Frontof(Q);
  for each neighbor v of u
  {
    Relax(u, v)

    if d(v) was updated by Relax and v not in the Q  //Here's where we're a bit smarter
        ADD v to End of Q.                           //since we add to Q if 
                                                     //the relaxation changed d(v)
  }
}

现在，如果所有最短路径最多有 k 个弧。那么最坏情况的运行时间是 O(V*k)，因为我们在这个智能版本中只经过 k 个弧。这比原来的 O(V*E) 快一点，因为 |k| < |E|

谁能告诉我这种改进版本不比原来的 Bellman-Ford 算法更好的图类型？也就是说，最佳情况下的性能是 O(V*E)

4

1 回答 1

0

考虑所有边都具有负权重的图。在这个图中，如果顶点 u 有多个传入边，它将被多次添加到 Q 中。

语句 |k| < |E| 不正确：如果图中存在负循环，则 k 是无限的

于 2012-12-29T12:59:53.863 回答