Guest User

Dijkstra using set

a guest
Feb 12th, 2011
455
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. vi D(N, 987654321);
  2.  
  3. // start vertex
  4. set<ii> Q;
  5. D[0] = 0;
  6. Q.insert(ii(0,0));
  7.  
  8. while(!Q.empty()) {
  9.  
  10.    // again, fetch the closest to start element
  11.    // from “queue” organized via set
  12.    ii top = *Q.begin();
  13.    Q.erase(Q.begin());
  14.    int v = top.second, d = top.first;
  15.  
  16.    // here we do not need to check whether the distance
  17.    // is perfect, because new vertices will always
  18.    // add up in proper way in this implementation
  19.  
  20.    tr(G[v], it) {
  21.         int v2 = it->first, cost = it->second;
  22.         if(D[v2] > D[v] + cost) {
  23.              // this operation can not be done with priority_queue,
  24.              // because it does not support DECREASE_KEY
  25.              if(D[v2] != 987654321) {
  26.                    Q.erase(Q.find(ii(D[v2],v2)));
  27.              }
  28.              D[v2] = D[v] + cost;
  29.              Q.insert(ii(D[v2], v2));
  30.         }
  31.    }
  32. }
RAW Paste Data