recategorized by
11,277 views
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?

  1. Weight $(u,v) \leq 12$
  2. Weight $(u,v) = 12$
  3. Weight $(u,v) \geq 12$
  4. Weight $(u,v) > 12$
recategorized by

4 Answers

Best answer
41 votes
41 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$.
edited by
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 

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 :)

Answer:

Related questions

5 votes
5 votes
3 answers
1
13 votes
13 votes
3 answers
3
Kathleen asked Sep 22, 2014
12,356 views
A common property of logic programming languages and functional languages is:both are procedural languages both are based on $\lambda$-calculusboth are declarativeboth us...