GATE IT 2007 | Question: 3, UGCNET-June2012-III: 34

Question

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?

• A. Weight $(u,v) \leq 12$
• B. Weight $(u,v) = 12$
• C. Weight $(u,v) \geq 12$
• D. Weight $(u,v) > 12$

Comments

Before looking at answer try to find answer using proof via contradiction or counterexample.

---

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.

---

nice explanation brother

Answer 1

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$.

Comments

Nice explanation...thanks

---

@ashutoshaay26 the question says that there exists an edge(u,v) in the graph but in your example there is no such edge....

 

---

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

Answer 2

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 

Answer 3

 

Above is an undirected weighted graph where shortest distance from source $S$ to $U$ is $53$  and $S$ to $V$ is $65$. Let's say $w(u,v)$ i.e edge weight from vertex u to v, is $x$ and take 2 cases.

Case $1:$ $x$ is strictly less than $12$.

---

When $w(u,v)$ is strictly less than $12$ then this contradicts that shortest distance from $S$ to $V$ is $65$, as now the shortest distance from $S$ to $V$ is $58$ (from $S \to U \to V$).

Therefore option A is false.

---

Case $2:$  $x$ is $12$ or greater than $12$.

When $w(u,v)$ is exactly $12$, the given info about shortest distances from source $S$ to $U$ and $V$ holds as still shortest distance from $S$ to $U$ is $53$, $S$ to $V$ is $65$, (also $65$ from $S \to U \to V$).

And if shortest distance info holds for $x=12$, then it'll also hold for $x > 12$.

Hence option $C$ is the answer.

Comments

Best answer

Answer 4

Answer : (C)

Answer 5

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 6

https://gateoverflow.in/?qa=blob&qa_blobid=13950177433133263720

 Handwriten solutions with diagram