稍微快一点的Bellman-Ford

Question

我对贝尔曼-福特做了一点修改，这样它只能“有用”放松。也就是说，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|

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

Answer 1

考虑所有边都有负重的图。在该图中，如果顶点u有多条输入边，它将多次添加到Q。

声明|k|