Biteration #3 Question 4 Wierd result

1

Hi everyone,

I was solving this question from the recent contest Biteration 3 . CodeChef: Practical coding for everyone

In djisktra algo , we always chose the minimum dis unvisited node in every iteration , so i had declared a done[] array to keep track of unvisited nodes and put the nodes in a priority queue . But using this approach gives WA.
https://www.codechef.com/viewsolution/34835048

Now , if I dont keep track of the unvisited nodes , then it somehow gives correct answer CodeChef: Practical coding for everyone

I am curious to know what is the reason for this behavior . Maybe if someone can point a testcase for difference.
Thanks

PS : In both the above submission please look at the section labelled as “See this section”

2

@bansalraghav19

3

I haven’t read the question, but a normal Dijkstra will work incorrectly if visited nodes are ignored (just for the sake of it) in future iterations. Say, you have a direct edge from source to another node P with weight W. But, say there exists a path with 2 edges through an intermediate node I (S - I - P) that gives a total sum smaller then W. You’ll need to update the smallest path to P and process it again, and not ignore it just because it was visited earlier.

You can only ignore an item in your priority queue if the distance it refers to is greater than the currently identified optimal distance. You might want to search for the concept of edge relaxation for more concrete examples.