A slightly faster Bellman-Ford

Question

I made a slight modification to Bellman-Ford so that it only does "useful" relaxes. That is, relaxations that meant d(v) was updated.

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

Now, if all shortest paths have at most k arcs. Then the worst-case runtime is O(V*k) since we only go through k arcs in this smart version. This is a bit faster than the original O(V*E) since |k| < |E|

Can anyone please tell me of a type of graph for which this improved version is no better than the original Bellman-Ford algorithm? That is, for which the best-case performance is O(V*E)

Answer 1

Consider the graph where all edges have negative weight. In this graph, vertex u will be added to Q multiple times if it has multiple incomming edges.

The statement |k| < |E| is incorect: if there is a negative loop in graph, then k is infinite