When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we need to use a custom comparator, but why in the case of set if we use pair of {node, distance} the code still works. Another problem is that if we use a set<pair<int,int>> s or if we use a set of set<pair<int,int>, greater<int,int>> s then also the code works perfectly, so does that mean when we use a set while doing Dijkstra's algorithm the order doesn't actually matter unlike the case of using priority queue for Dijkstra's algo?
2
-
$\begingroup$ How do you select the next element to remove from the set? $\endgroup$– StevenCommented Jul 26, 2022 at 10:56
-
$\begingroup$ I select the first element from the set everytime. $\endgroup$– Rasmus INCommented Jul 26, 2022 at 10:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
In general: yes. The correctness of Dijkstra's algorithm does depend on the order in which elements are extracted from the priority queue. You do need to extract them in non-decreasing order of their tentative distance (at extraction time).
Your particular question depends on the details of the STL library, so I'm not sure it's suited for this website.
That said, std::set is a sorted collection of elements and the default comparator for std::set<T> is std::less<T>. In your case T is std::pair<int, int> (where the first int is the node "name", and the second int is the node's tentative distance) and std::pairs are compared lexicographically.
Therefore you are extracting the node with the smallest "name", regardless of its current tentative distance. The resulting implementation of Dijkstra's algorithm is not correct, since you are breaking the property guaranteeing that, when you extract a node, it's current tentative distance in the algorithm coincides with the actual distance in the graph.
In fact, the algorithm fails even for unweighted undirected graphs and even if you relax distances towards nodes that have already been extracted (but do not re-add them to the set since, if you did, you'd be losing the time complexity guarantees of Dijkstra's algorithm). An an example consider the graph $(\{0,1,2,3,4\}, \{ (0,1), (1,2), (2,3), (0,4), (4,2) \})$ and source vertex $0$.
-
$\begingroup$ In my code the pair<int,int> , pair was of <node, distance> and not <distance, node> so everytime the first value I am extracting is not on the basis of smallest distance but on the basis of smallest value node. Another thing whenever I am in need to update distance for a certain node, I am checking whether there's already a pair for that corresponding node in the set, if there I am first removing from the set and then I am adding the pair for the node with the new updated distance. However the same approach fails in case of priority queue, If do the same operation it gives me a wrong ans. $\endgroup$ Commented Jul 26, 2022 at 11:42
-
$\begingroup$ Can you please tell even though my code is not mainting the order but still gets submitted in the online coding platforms? $\endgroup$ Commented Jul 26, 2022 at 11:56
-
$\begingroup$ Sorry, I don't know what you want to know. I see no question. $\endgroup$– StevenCommented Jul 26, 2022 at 12:03
-
$\begingroup$ My doubt is as you said order does matter and also at extraction time we need to get the node with smallest distance, but then why if I doesn't maintain order in a set the code gets submitted while the same approach in priority queue fails. So is there any difference between the two? $\endgroup$ Commented Jul 26, 2022 at 12:07
-
$\begingroup$ If you are getting different outputs there must necessarily be a difference. However you seem to think that if your program passes the validation of some automated test system, them it must be correct. This is not the case. Both versions can be wrong. A wrong algorithm can return the correct answer on infinitely many instances. $\endgroup$– StevenCommented Jul 26, 2022 at 12:09