electro177's blog

Doubt in implementation of Dijkstra Algorithm
By electro177, history, 3 years ago, In English 
priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
  pq.push({0, 0});
  memset(d, 0x3f, sizeof(d));
  d[0] = 0;
  while (pq.size()) {
    ar<ll, 2>    u = pq.top(); 
    pq.pop();
    
    if ( u [0]  > d[ u[1] ] ) // i have a doubt here
      continue;
    
    for (ar<ll, 2> v : adj[u[1]]) {

      if (d[v[1]] > u[0] + v[0]) {
        d[v[1]] = u[0] + v[0];
        pq.push({d[v[1]], v[1]});
      }


    }
  }

I do not understand why if ( u [0] > d[ u[1] ] ) continue; in the code .please give the reason ,is it related to connected component?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You cannot efficiently erase an element from the priority queue.

Let's start from node 1. Suppose you start from node 1, and there 1->2, 2->3, 1->3 edges.

Then at the first iteration 2, 3 are pushed into the queue, but at the second iteration (node 2), if 1->2 + 2->3 is better than 1->3, 3 would be pushed into the queue again. The continue part takes care of situations like this. Since if u[0]>d[u[1]] then you would have processed pq.top() = {d[u[1]], u[1]} before, you simply don't need the iteration for this same vertex again so just continue.

→ Reply