34 votes 34 votes Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight 53 and the shortest path from $s$ to $v$ has weight 65. Which one of the following statements is always TRUE?Weight $(u,v) \leq 12$Weight $(u,v) = 12$Weight $(u,v) \geq 12$Weight $(u,v) > 12$ Algorithms gateit-2007 algorithms graph-algorithms normal ugcnetcse-june2012-paper3 shortest-path + – Ishrat Jahan asked Oct 29, 2014 • recategorized Oct 23, 2018 by Pooja Khatri Ishrat Jahan 11.7k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Chhotu commented Aug 28, 2017 i edited by Chhotu Aug 28, 2017 reply Follow Share Before looking at answer try to find answer using proof via contradiction or counterexample. 6 votes 6 votes JashanArora commented Mar 3, 2020 reply Follow Share s to u = 53 s to v = 65 Difference = 12. If u to v was 5 (less than 12), then we could simply have gone from s to u, then u to v (53+5=58). But min distance between s to v is 65. So, u to v can't be less than 12. 7 votes 7 votes Please log in or register to add a comment.
Best answer 42 votes 42 votes C. Weight $(u,v) \geq 12$ If weight $(u, v) < 12$, then the min. weight of $(s, v) = $weight of $(s, u) + $ weight of $(u, v) = 53 + (<12) $ will be less than $65$. Arjun answered Jan 18, 2015 • edited Oct 26, 2017 by kenzou Arjun comment Share Follow See all 28 Comments See all 28 28 Comments reply Pradip Nichite commented Dec 4, 2015 reply Follow Share Hi Arjun, Why Not ans B: 0 votes 0 votes Akash Kanase commented Dec 17, 2015 reply Follow Share It is not B because if weight (u, v) ≤ 12 then you can put weight(u,v) = 1. Then you get path of cost 54 from S->u->v, which should not have been posisible as we have already got the path from S-> u-> V ! 7 votes 7 votes srestha commented Dec 7, 2016 reply Follow Share Ans is C) rt? D) is only >12, not = 1 votes 1 votes alpha commented Dec 8, 2016 reply Follow Share Same here i also think the Answer is C ..because in D equals make two shortest path possible S->u->V or S->V..but in question shortest given is from S->V...please comment the correct answer 1 votes 1 votes Lokesh . commented Dec 12, 2016 reply Follow Share that's a typo....answer is C 1 votes 1 votes rajan commented Jan 4, 2017 reply Follow Share @arjun sir i did not get above comment but igot only one thing here which is the shortest path from s to v is given 65 . that means to maintain it we can have the value from u to v is <=12 means C . but not D bcz we left one case which is equal to 12 0 votes 0 votes shweta1920 commented Apr 29, 2017 reply Follow Share I DID NOT GET WHAT U EXPLAINED ABOVE .. PLZ ELABORATE 0 votes 0 votes Bongbirdie commented May 24, 2017 reply Follow Share Why can't the answer be (D)? Strictly increasing will be more preferable right ? 1 votes 1 votes Bongbirdie commented May 24, 2017 reply Follow Share Why do we need '=' ? 0 votes 0 votes SKP commented Jun 23, 2017 reply Follow Share We need "=" becoz different algorithms may take different path. 0 votes 0 votes akash.dinkar12 commented Jul 14, 2017 reply Follow Share @Arjun sir why not option D????? 1 votes 1 votes srestha commented Jul 14, 2017 reply Follow Share weight should be =12 and >12. So, C) is more appropriate answer than D) 0 votes 0 votes akash.dinkar12 commented Jul 14, 2017 i edited by srestha Jul 14, 2017 reply Follow Share @Srestha They have given that that already the shortest distance from S to U = 53 and S to V=65, mean they both are true statements rt !!!! So, t think question is about relaxing the edge if we take Edge(U-V) is 12 then there would be chances that S can go through UV edge to reach to the V then the statement S to V=65 will be wrong, But it is already true so we can't make it false 1 votes 1 votes srestha commented Jul 14, 2017 reply Follow Share U r using distance vector routing algo. right? 1 votes 1 votes srestha commented Jul 15, 2017 reply Follow Share @ akash.dinkar12 yes I think ur point is correct. and shortest path should be unique too. So, yes D) should be answer 1 votes 1 votes akash.dinkar12 commented Jul 15, 2017 reply Follow Share @srestha yes, that is why I was saying.so plz confirm it... 0 votes 0 votes Bongbirdie commented Jul 15, 2017 reply Follow Share @Akash and @Sreshta The answer given is Option(C) only. Even I had this doubt earlier why the '=' is required but then reached the following conclusion. It is already found that the shortest distance between s to v is 65 and s to u is 12. So, yes this is true that w(u,v)>12. But even if we find w(u,v) to be 12, since already the shortest distance is found, it won't get modified. So, we can have w(u,v)>=12. Recall Dijkstra's Algo, once the shortest distance is found, even if the same distance is again obtained, we won't change it. Since we must choose the best answer, (C) is the answer. ((C) and (D) both are true but option (C) is more specific so it's better that (D)). 7 votes 7 votes akash.dinkar12 commented Jul 15, 2017 reply Follow Share Reference:https://courses.csail.mit.edu/6.006/fall11/lectures/lecture16.pdf Even if I put w(u,v)=12 then also relaxing of the edge will not occur.so known statement which is given in statement is true. Now I think Option C is more correct... 4 votes 4 votes ashutoshaay26 commented Jul 16, 2017 reply Follow Share Answer is : C For '=' sign: check this scenario For '>' sign: check this scenario Let me know if you have any other doubt! 24 votes 24 votes srestha commented Jul 16, 2017 reply Follow Share yes u r right See this ques https://gateoverflow.in/118306/gate2017-1-26 @akash @ Bongbirdie ur doubt will be clear shortest path of a graph maynot be unique, but MST should be unique. 1 votes 1 votes sushmita commented Aug 31, 2017 reply Follow Share because more than one path may exist. 0 votes 0 votes set2018 commented Nov 12, 2017 reply Follow Share srestha sushmita i have a doubt.As in question it is already mention uv is edge then why we are considering > this case. 0 votes 0 votes srestha commented Mar 3, 2018 reply Follow Share @set2018 edge exists means that edge doesnot change shortest path of the graph 0 votes 0 votes Nitesh Singh 2 commented Jul 10, 2018 reply Follow Share If You think answer should be D. Then you surely haven't got the question correctly. Understand the question clearly. 0 votes 0 votes HeadShot commented Jan 12, 2019 reply Follow Share @Bongbirdie your statement isnt correct. Its not mentioned that which algo is used. If we use bellman ford then we will repeatedly check for shortest path. @akash.dinkar12 gave a correct reasoning, its just ,even if its equal we wont change. 0 votes 0 votes AcidBurn commented May 31, 2019 reply Follow Share Nice explanation...thanks 0 votes 0 votes Deterministic commented Sep 30, 2019 reply Follow Share @ashutoshaay26 the question says that there exists an edge(u,v) in the graph but in your example there is no such edge.... 0 votes 0 votes Abir Mazumder commented Apr 11, 2020 reply Follow Share The trick in this question is that no one has mentioned whether the edge (u,v) is included or excluded in the before mentioned shortest path . This means the shortest path from s to v may or may not include the edge (u,v) , hence ">=" is more appropriate than ">" as it allows Djikstra's algo to either choose a path from s to v with or without including u 4 votes 4 votes Please log in or register to add a comment.
1 votes 1 votes reference : cormen shortest path : d since (u,v) is an edge in graph d (s,v) <= d (s,u) + w (u,v) // w : weight of edge (u,v) 65 <= 53 + w (u,v) w (u,v) >= 12 This equation simply says that the shortest distance from s to v cannot be more than the (shortest distance from s to u + including the weight of edge uv ( if v is discovered via u in bfs ) ) . It also tells about the bound on the weight of edge uv. This edge is rejected when it doesn’t helps in minimizing the path including vertex u and v from s zoy123 answered Dec 12, 2022 zoy123 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Ans = C Make a graph which has direct edge from ‘s’ to ‘v’ ,now consider this as shortest path from ‘s’ to ‘v’ which is given as 65 ,no we know that if this is the shortest path then the another path from ‘s ‘ to ‘v’ via 'u' will be “ greater then equal to “ as it can be same or greater ,simple logical answer :) Ritik gupta answered May 2, 2021 Ritik gupta comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Answer : (C) ritiksri8 answered Mar 21 ritiksri8 comment Share Follow See all 0 reply Please log in or register to add a comment.