0 votes 0 votes The answer they have given is 2, but i think it should be 1, can someone verify? Algorithms dijkstras-algorithm algorithms made-easy-test-series + – palashbehra5 asked Jan 11, 2022 palashbehra5 700 views answer comment Share Follow See 1 comment See all 1 1 comment reply Isha_99 commented Jan 11, 2022 reply Follow Share I am also getting 2 ,shortest distance using Dijkstra as 9 and Bellman Ford as 7. Hence difference as 2 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes Hence Difference is 9 -7 = 2 Isha_99 answered Jan 11, 2022 Isha_99 comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments Isha_99 commented Jan 11, 2022 reply Follow Share See for the question you have asked initially @Zack Fair has already commented the graph with visit time and finish time refer it once. 1 votes 1 votes palashbehra5 commented Jan 11, 2022 i edited by palashbehra5 Jan 12, 2022 reply Follow Share is in Dijkstra’s algorithm,as once we update a node we remove it from data structure like heap of unvisited node . @Isha_99 True, However, say it's G which has been extracted out of the min-heap now. For all V adjacent to G : if( V.d > G.d + W(G,V)) V.d = G.d + W(G,V)This shouldn't stop distances from getting updated right. Source Cormen. 0 votes 0 votes Isha_99 commented Jan 11, 2022 reply Follow Share I think you are right @palashbehra5 Since all v adjacent to G are being relaxed hence J will also be relaxed to 8 . Although we will not be able to use this updated value of J further to update again edges going out from J . Thanks for pointing out my mistake . 1 votes 1 votes Please log in or register to add a comment.