Zeal Test Series 2019: Algorithms - Minimum Spanning Trees

Question

How many of following are correct statements ?

(i) A graph where all edge weights are distinct can have more than one shortest path between  two vertices u and v

(ii)adding a number w on weight of every edge of graph might change the graph’s minimum spanning tree(Assume that all edge weights of graph are distinct)

(iii)multiplying all edge weights by a positive number might change the shortest path between  two vertices u and v (Assume that all edge weights of graph are distinct)

Comments

.1

---

bro are you sure about it  ??

---

@Magma haaa 1) will be true 2) and 3) will be false as all the edges have distinct edge weights.

---

thanks

---

Arvin for second can you show any example i got only 1

---

suppose we have a triangle having ab=1,bc=2,ac=3 and distance between ac=3 either u choose ab+bc or ac and u took ab+bc as shortest path for your case. now if u add all three sides by +1 then ab=2 bc=3 ac=4 so ab+bc=5>4 (ac).

so your shortest path changed na now as you have to go by ac..

---

@Arvin YEAH  GOT IT

---

Option 2 is talking about minimum spanning tree not the shortest path

---

@Registered user 48 thanku brother yes there will be only one true statement..

---

Yeah it's minimum spanning tree means only 1 is correct