void dijkstra(int v){
fill(d,d + n, inf);
d[v] = 0;
int u;
set<pair<int,int> > s;
s.insert({d[v], v});
while(!s.empty()){
u = s.begin() -> second;
s.erase(s.begin());
for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight)
if(d[p.first] > d[u] + p.second){
s.erase({d[p.first], p.first});
d[p.first] = d[u] + p.second;
s.insert({d[p.first], p.first});
}
}
}
I managed to implement Dijkstra’s algorithm using heaps but it was extremely long, so I decided to try implementing using sets. However, in the above implementation (source: CF), I was unable to understand the part for(auto p: adj[u]) and the stuff in the loop. I haven’t manipulated a set of pairs or priority queue of pairs before, I understand this is c++11 usage, but now how it works. Could someone please explain, and if possible, provide an equivalent non c++11 statement?
Looks like you understand Djikstra’s algorithm but are not familiar with the Standard template library in C++.
Topcoder tutorials are the best resource to get started with STL.
Regarding the part you didn’t understand, I’ll try to explain it line by line with equivalent priority_queue statements.
Read this only after reading the tutorial or you won’t understand completely!
void dijkstra(int v){
fill(d,d + n, inf);//fill entries with some big value
d[v] = 0;//distance from starting vertex to starting vertex is zero
int u;
set<pair<int,int> > s;//a set of pairs(read the tutorial to understand this part)
/*priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
by default the priority queue is a max-heap.
since we need a min-heap we use the inbuilt-function "greater"*/
s.insert({d[v], v});// insert the starting vertex in the set
// set maintains the elements in increasing order
// That's why we did s.insert({d[v],v}); and not s.insert({v,d[v]});
// by default the pairs are sorted by the first value (if the first values are equal then by the second value)
/* In the priority_queue we'll do Q.push({d[v],v});*/
// FYI "{}" notation is the same as make_pair notation you would have read about .
// so s.insert(make_pair(a,b)) is equivalent to s.insert({a,b});
while(!s.empty()){//terminate when the set is empty
/*same for the queue while(!Q.empty())*/
u = s.begin() -> second;// s.begin() basically is a pointer to the first entry in the set(one with the minimum d[v] value)
// Oh and you can access the pair elements like this
// pair<int,int> p = {a,b};
// int x = p.first //first entry of the pair
//int y = p.second; //second entry of the pair
// so u basically is the second entry of the pair (vertex with minimum d[] value )
/*u = Q.top().second for the priority_queue*/
s.erase(s.begin());//remove this entry from the set
/*for priority_queue Q.pop();*/
for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight)
// adj[u] is a vector of pairs
// so to iterate a vector of pairs the iterator should be a pair (p is a pair here )
// this is equivalent to for(pair<int,int>::iterator it = adj[u].begin();it!=adj[u].end();it++)
// see how much shorter the code becomes if you use auto keyword :D
// It's very useful if you have something complex to iterate like pair<string,pair<int,pair<int,int>>> :P
if(d[p.first] > d[u] + p.second){// p.first is the distance (remember we pushed {d[v],v}) ?!, p.second is the vertex
s.erase({d[p.first], p.first});// we found a shorter distance to the vertex p.first
// we need to update it
// for updating in set , remove the old entry , insert the new entry
d[p.first] = d[u] + p.second;//update the distance to this node
s.insert({d[p.first], p.first});//insert new entry (new distance to the vertex)
/*for priority_queue we would have just pushed the new entry Q.push({d[p.first], p.first})*/
}
}
}
/*P.S : for priority_queue we would need to additionally maintain an array visited[] to keep track of nodes we have already pushed to the queue.
We don't need this in set as set inserts a new entry only if it doesn't exist already */
3 Likes
Thanks a lot 
This was damn useful, especially with INOI just a few days away
Glad to hear that! Just read the topcoder tutorial i mentioned and it will become crystal clear 
1 Like
Thanks a ton @sarvagya3943 for taking the pain to explain it in such great detail!