I went through the editorial of CLIQUED APRIL17 Challenge problem, editorials use set to implement dijkstra’s algorithm, I have always used priority queue to implement dijkstra’s algorithm, does using set have any added advantage, does it optimise the code to some extent?
2 Likes
No, both have the same complexity of O(n log n) so u can use either of them
3 Likes
Disclaimer: I’m sorry for asking my own question below someone else’s question, and this is so because I’m not allowed to ask questions as I don’t possess enough karma. Though I’m new here.
I participated in my first Codechef contest, April Challenge 2017, last week and now I again wish to solve those problems which I couldn’t solve last time, but I don’t see any link for submission on the page where I had access to last time. Do I have to search whole website for each problem of “April Challenge 2017” by their problem code? Any counsel would be highly appreciated.
8 Likes
Problems during contest have the URL format: www.codechef.com/CONTESTCODE/problems/PROBLEMCODE
And practice problems have the URL format: www.codechef.com/problems/PROBLEMCODE
So it’s quite easy to find a problem for practice after the contest ends 
5 Likes
No both priority queue and set have some complexity for operations though set can at the same time report both max and min values but priority queue arranges according to the way we want the data to be arranged (min/max heap).
Priority queues using binary heaps have a similar complexities for most operations as priority queues using sets.
But the constants are smaller for binary heaps, which is reason why usually a binary heap is used for Dijkstra in textbooks. The priority_heap in C++, however, doesn’t support a update_key operation that is useful for Dijkstra, as this also requires something to locate the key first. Binary heaps with update_key and a hash for locating a key can have lower constants than using a set, but using a set or a map as the queue provides the same asymptotic complexity and a much simpler implementation, than coding your own binary heap with update_key and a hash to locate the key.
You can also check the editorial, it has both contest and practice links, or you can also use google chrome find option to find the problem after going to find the particular problem section ie easy medium hard. These are an addition what @meooow stated.
2 Likes
It is not necessary to implement one’s own heap with this additional hash feature. One can use a standard library heap for Dijkstra’s algorithm by pushing a new distance value for the same vertex when relaxing, and the simply considering the first time a distance for a particular vertex is popped from the heap and rejecting the subsequent ones since they are guaranteed to be larger distance values for that vertex that were inserted before the final relaxation.
1 Like
@nanoalpaca I’ve never used key-value pair in priority queue to implement dijkstra’s algo, please look through my code to understand that http://ideone.com/HhHGv1. I don’t know regarding set, how it is implemented but priority queue doesn’t require key value pair to manipulate the edge weights.