63 votes 63 votes Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices Algorithms gatecse-2008 algorithms graph-algorithms normal + – Kathleen asked Sep 12, 2014 edited Jun 14, 2019 by Lakshman Bhaiya Kathleen 27.3k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Pranavpurkar commented Sep 14, 2021 reply Follow Share @yogesh88 Dijkstra will surely fail in the case of negative edge wt cycle . 5 votes 5 votes iamjha007 commented Oct 13, 2021 reply Follow Share @ASNR1010 the order of selection of edge is: 𝐚 𝐛 𝐞 𝐟 𝐠 𝐜 𝐡 𝐝 3 votes 3 votes mayank_1 commented Jan 6 reply Follow Share @Pranavpurkar Yes True iff it is reachable form source vertex 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Dijkstra algorithm fails when the graph contains negative weight cycle forms . The graph contains only negative weights then the dijkstra gives correct shortest paths from source to every edge. so the answer is D. Nagamani answered Jan 26, 2018 Nagamani comment Share Follow See 1 comment See all 1 1 comment reply Pranavpurkar commented Sep 14, 2021 reply Follow Share no this is not totally correct..in case of negative edge wts ...dijkstra may or may not give correct shortest paths. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Dijkstra's single source shortest path algorithm here this works fine bcoz there is no -ve weight cycle in graph. _xor_ answered Jun 5, 2015 _xor_ comment Share Follow See all 2 Comments See all 2 2 Comments reply Gaurav Sharma commented Jan 23, 2016 reply Follow Share D is the correct option, but the explanation you have provided does not seem right. 4 votes 4 votes Ahwan commented Jul 20, 2017 reply Follow Share Just see the diagram by Sachin Mittal bro. Even if there is no negative weight cycle still only negative edges can also give wrong answer. So if they are asking about shortest path with negative edges then there is no method or rule except applying Dikastras algo & verifying manually if it is the correct answer. 4 votes 4 votes Please log in or register to add a comment.
0 votes 0 votes Dijkstra Algorithm fails for negative-edge-weight-cycle, but, here there is no negative-edge-weight cycle. So, it computes shortest path distance to all vertices. Ans: D Gaurav Yadav answered Jun 7, 2020 Gaurav Yadav comment Share Follow See 1 comment See all 1 1 comment reply -RahulKumar- commented Oct 21, 2023 reply Follow Share Correct. Just adding one more point here that Dijkstra’s Algorithm may or may not give correct answer upon $-ve$ edges. In this question, it may have. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Node : distance, parent Dij run gives this : A : 0, NIL B : 1,a C :3c D : 6c E : -2b F : -1e G :2f H :-2c Which are in fact correct if you observe the graph. So, all vertices got luckily correct in this example. thewolf answered Oct 5, 2020 thewolf comment Share Follow See 1 comment See all 1 1 comment reply SkillIssue commented Mar 9 reply Follow Share It should be F: 0e isnt it? 0 votes 0 votes Please log in or register to add a comment.