You are not logged in. Please login at www.codechef.com to post your questions!

×

What is advantage of using set over priority_queue for dijkstra's algorithm?

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

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

edited 18 Apr '17, 20:09


Answer is hidden as author is suspended. Click here to view.

answered 18 Apr '17, 20:38

ardentcoder's gravatar image

2★ardentcoder
(suspended)
accept rate: 15%

5

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 :)

(18 Apr '17, 20:54) meooow ♦6★
2

@meooow, That seems to be working with ease. Thank you.

(18 Apr '17, 21:07) ardentcoder2★
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) neilit19923★

No, both have the same complexity of O(n log n) so u can use either of them

link

answered 18 Apr '17, 20:25

mathecodician's gravatar image

6★mathecodician
2.6k1932
accept rate: 7%

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).

link

answered 18 Apr '17, 21:19

vidit_123's gravatar image

1★vidit_123
1036
accept rate: 5%

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.

link

answered 18 Apr '17, 21:31

nanoalpaca's gravatar image

6★nanoalpaca
22613
accept rate: 7%

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) meooow ♦6★

@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.

(19 Apr '17, 19:02) neilit19923★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,351
×124
×27

question asked: 18 Apr '17, 20:09

question was seen: 668 times

last updated: 19 Apr '17, 19:03