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.

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

Hi Arjun, Why Not ans B:

---

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 !

---

Ans is C) rt?

D) is only >12, not =

---

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

---

that's a typo....answer is C

---

@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

---

I DID NOT GET WHAT U EXPLAINED ABOVE .. PLZ ELABORATE

---

Why can't the answer be (D)? Strictly increasing will be more preferable right ?

---

Why do we need '=' ?

---

We need "=" becoz different algorithms may take different path.

---

@Arjun sir why not option D?????

---

weight should be =12 and >12. So, C) is more appropriate answer than D)

---

@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

---

U r using distance vector routing algo. right?

---

@ akash.dinkar12

yes I think ur point is correct. and shortest path should be unique too.

So, yes D) should be answer

---

@srestha

yes, that is why I was saying.so plz confirm it...

---

@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)).

---

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

---

Answer is : C

For '=' sign: check this scenario 

For '>' sign: check this scenario 

Let me know if you have any other doubt!

---

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.

---

because more than one path may exist.

---

 srestha  sushmita 

i have a doubt.As in question it is already mention uv is edge then why we are considering > this case.

---

@set2018

edge exists means that edge doesnot change shortest path of the graph

---

If You think answer should be D. Then you surely haven't got the question correctly. Understand the question clearly.

---

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

---

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

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 4

Answer : (C)