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 667 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 palashbehra5 commented Jan 11, 2022 reply Follow Share why is the path not A-C-F-G-J instead? I understand it could be due to the presence of a negative edge, but it still ends up getting relaxed right? 0 votes 0 votes Isha_99 commented Jan 11, 2022 reply Follow Share Yes you are right , A-C-F-G path gives shortest path as 8 due to presence of negative edge DH , but tell me can we relax a vertex again after visiting it once ? Even if we relax it, we aren’t allowed to update the new distance in it . So I think considering this, 9 is the value of shortest path possible using Dijkstra . 1 votes 1 votes Zack Fair commented Jan 11, 2022 i edited by Zack Fair Jan 11, 2022 reply Follow Share right the sequence in which vertex are removed and corresponding length at the time are like this, the indicators are [sequence number of deletion of node : distance at time of removal] 1 votes 1 votes palashbehra5 commented Jan 11, 2022 reply Follow Share Zack Fair I meant that in the case of Dijkstra's algorithm.Isha_99 You mean edge relaxation, right?"Even if we relax it, we aren’t allowed to update the new distance in it ." Why? 0 votes 0 votes Zack Fair commented Jan 11, 2022 reply Follow Share palashbehra5 I have the same doubt that if we are relaxing edges anyway then why it can’t update the distance. The reason I could think of is because we have deleted the node from data structure (heap /priority queue) it could have something to do with it. Since the node is not in heap we can not update? 1 votes 1 votes palashbehra5 commented Jan 11, 2022 reply Follow Share I believe if theres going to be any error in this case, it will be due to -9 weighted edge, as it updates the shortest path late. Without -9 as edge. With -9, it shows the shortest path should have been 7 instead. Online tool used : https://visualgo.net/en/sssp 0 votes 0 votes palashbehra5 commented Jan 11, 2022 reply Follow Share Zack FairWhat should be the SSSP in this case, no -ve edges here right? 0 votes 0 votes Isha_99 commented Jan 11, 2022 reply Follow Share @Zack Fair You are right . @palashbehra5 The answer of not updating the vertex again , is in Dijkstra’s algorithm,as once we update a node we remove it from data structure like heap of unvisited node . 1 votes 1 votes palashbehra5 commented Jan 11, 2022 reply Follow Share Isha_99 And which vertex is being updated/revisited again in the above case? I don't think I am able to follow. 0 votes 0 votes Zack Fair commented Jan 11, 2022 reply Follow Share since there is no negative edge Dijkastra’s algorithm should work fine so for node $3$ distance would be $5$ deletion sequence would be $0→ 2→ 1→ 3$ 0 votes 0 votes Zack Fair commented Jan 11, 2022 reply Follow Share Oh , I tried the resource you mentioned and it turns out it does update the distance on relaxation , just doesn't use it / can't use it.(The above conclusion is drawn from the fact that even after vertex 2 was deleted it was correctly updated , just it wasn't in data structure to be used anymore) 0 votes 0 votes palashbehra5 commented Jan 11, 2022 reply Follow Share @Zack Fair Right, only the vertices whose all adjacent has been relaxed, are deleted from the heap, then what I don't understand is why can't we update GJ? As, G was being visited for the first time, and 8<9 so update.Edit #1: Saw your image, and right, that is how it is expected to work. However, the question is not about incorrect/correct shortest paths, it is about Dijkstra's and bellman ford's result on the given graph, for which I think 1 GJ should have been relaxed. 0 votes 0 votes 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.