Dijkstra's algorithm using STL set

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 :slight_smile: 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 :smiley:

1 Like

Thanks a ton @sarvagya3943 for taking the pain to explain it in such great detail! :smiley: