Dijkstra's algortihm code doubt

#1

aren’t the nodes for which shortest path from the source is already found out being visited again?

#2

for the code which is shown in tutorial

#3

Hey @jhaprashant5222
can u please confirm if this is the same method discussed in the vedio : https://ide.codingblocks.com/s/148003?_ga=2.234019038.1951668522.1605367099-1795954092.1597348154

#4

Okay ,so we will never revisit and node again which we removed from the beginning of set because there will be no negative edges so the one which we are removing cant have any shorter distance in graph.

We don’t use dijksta with negative weights .Refer to this for more info regarding it : https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges

#5

but we are checking for the node whose shortest distance is already known , doesn’t this increase time complexity?

#6

But we have to check somehow right otherwise how will we know which ones are visited or not
Even if u maintain a visited array u will always check if neighbor is visited or not
So this is a standard algorithm we follow
U have to understand the idea behind it that how we are getting shortest distance

#7

and why set is preferred than the priority queue?

#8

set is preferred than the priority queue ( this part I couldn’t understand in tutorial)

#9

Hey
You can use either.
Set may give a better runtime as in that we can erase any element, thus we can remove any redundant ones as we get them, but in priority_queue we can only remove top.

we used sets for the ease of implementation , as the priority_queue in the stl lacks some properties we need for dijstras. the major advantage we have using set(stl) is the ability to update, insert and delete the unique values and store in ordered manner. set provides us set.find() method which takes the value and finds if the value is present or not in the set . if present then it return the address of element in the set and if not then provides the address of set.end() . but in priority _queue(stl) we don’t have this property available to us.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.