Bellman-Ford variation

Question

I have a smarter version of Bellman-Ford here:

    //Queue Q; source s; vertices u, v
    Q ← s // Q holds vertices whose d(v) values have been updated recently.
    While (Q !empty)
    {

    u ← Dequeue(Q)

     for each neighbor v of u
     {
        Relax(u, v)
        if d(v) was updated by Relax and v not in Q
           Enqueue(v)
     }
   }

Can anyone think of a type of graph for which this algorithm is lower bounded by (V*E) time complexity where v = #vertices, E = #edges

I want to see where the pitfalls of this are.

Answer 1

It's been years since I last thought about short path algorithms, correct me if I forgot something.

First, we'll start by ruling out the negative-weighted cycle case, but it can be a source of worst-case performance.

Let's suppose you visit a complete graph. From the first node, you'll queue V-1 nodes, because all of the nodes are neighbours to s. Let's suppose you are unlucky, and that the last node you queue is part of the shortest path to all the nodes. As a consequence, you'll have to queue V-2 nodes (all of them, minus the source node and the one you are evaluating...). Now let's be extremely unlucky, and suppose that the last node you queue is again part of the path to all the remaining nodes... You'll have to queue V-3 nodes, etc.

So if everything goes wrong, you'll have evaluated V-1*V-2*...*3*2*1 nodes. You should easily find out how this sums to |E|.

For each node, what are you doing ? doing a check on each of it's neighbours. Each node has V-1 neighbours.

We're already at O(|V-1||E|) worst-case complexity for your algorithm. If I remember well, the Bellman-Ford algorithm checks each edge to make sure there is no negative-weighted cycle, and so should you ; and that adds 1 to V-1, aka (|V||E|) worst-case complexity.

Answer 2

I'm not sure this works, but assuming it does, you can create a case where BF offers no improvement. Create start and end node and in between put N vertices connecting the two. The algorithm will still have to consider every path.

Answer 3

This is an improvement for Ford-Bellman. It implement faster than normally. Of course, in worst case, time complexity can be O(n.m). But, it is very hard to create an input to hack this algorithm. In contests, Ford-Bellman with queue executes FASTER than Dijkstra. BUT, you must create an array call Inqueue to check if current element was in queue :

qu : queue;
inqueue : array of bool;

for i in [1..n] do { d[i]=oo; inqueue[i]=false; }
qu.push(start);
d[start] = 0;

repeat
    u=qu.pop;
    inqueue[u]=false;
    for v in adj[u] do
    if minimize(d[v], d[u]+uv) then
    if !inqueue[v] then
    { inqueue[v] = true; qu.push(v); }
until qu.empty;
print d[target];