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.6k 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. 6 votes 6 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 Show 25 previous comments 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.