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? asked 18 Apr '17, 20:09

Answer is hidden as author is suspended. Click here to view.
answered 18 Apr '17, 20:38
5
Problems during contest have the URL format:
(18 Apr '17, 20:54)
2
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.
(18 Apr '17, 22:59)

No, both have the same complexity of O(n log n) so u can use either of them answered 18 Apr '17, 20:25

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). answered 18 Apr '17, 21:19

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. answered 18 Apr '17, 21:31
1
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.
(19 Apr '17, 01:24)
@nanoalpaca I've never used keyvalue 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.
(19 Apr '17, 19:02)
