Doubt in implementation of Dijkstra Algorithm

Revision en1, by electro177, 2021-06-27 17:35:49
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?

Tags #implementaion, silly, #help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English electro177 2021-06-27 17:35:49 673 Initial revision (published)