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?
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.
@ashutoshaay26 the question says that there exists an edge(u,v) in the graph but in your example there is no such edge....
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
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 :)
Answer : (C)
64.3k questions
77.9k answers
244k comments
80.0k users