Timeline for Does order of elements in a set matter in Dijkstra's Algorithm?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2022 at 17:59 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 26, 2022 at 13:23 | comment | added | Steven | That's a more general version of a well-known NP-hard problem. There is no known polynomial-time algorithm for that. | |
| Jul 26, 2022 at 13:22 | comment | added | Rasmus IN | Longest simple path from a source node to all other nodes in a graph | |
| Jul 26, 2022 at 12:50 | comment | added | Steven | I don't undrstand what is the problem you want to solve. Are you after the longest simple path in a graph? Or the eccentricity of a single source? Or the diameter or the graph? | |
| Jul 26, 2022 at 12:14 | comment | added | Rasmus IN | Thank You for the clarification. I got it. One thing suppose if I use Dijkstra for finding the largest distance paths, can a max heap or a set where elements sorted in descending order ( set<pair<int,int>,greater<pair<int,int>>> work? Provided the weights are not negative. It would be help if you can help in this regard. | |
| Jul 26, 2022 at 12:09 | comment | added | Steven | 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. | |
| Jul 26, 2022 at 12:07 | comment | added | Rasmus IN | 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? | |
| Jul 26, 2022 at 12:03 | comment | added | Steven | Sorry, I don't know what you want to know. I see no question. | |
| Jul 26, 2022 at 11:56 | comment | added | Rasmus IN | Can you please tell even though my code is not mainting the order but still gets submitted in the online coding platforms? | |
| Jul 26, 2022 at 11:50 | history | edited | Steven | CC BY-SA 4.0 |
added 98 characters in body
|
| Jul 26, 2022 at 11:42 | comment | added | Rasmus IN | 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. | |
| Jul 26, 2022 at 11:26 | history | edited | Steven | CC BY-SA 4.0 |
added 258 characters in body
|
| Jul 26, 2022 at 11:18 | history | edited | Steven | CC BY-SA 4.0 |
added 351 characters in body
|
| Jul 26, 2022 at 11:07 | history | answered | Steven | CC BY-SA 4.0 |