-
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/ are TRUE ?
P : Minimum spanning tree of G does not change
Q : Shortest path between any pair of vertices does not change
-
- P only
- Q only
- Neither P nor Q
- Both P and Q
- P only
Correct Option: A
The shortest path may change. The reason is, there may be different number of edges in different paths from s to t. For example, let shortest path be of weight 10 and has 5 edges. Let there be another path with 2 edges and total weight 25. The weight of the shortest path is increased by 5*10 and becomes 10 + 50. Weight of the other path is increased by 2*10 and becomes 25 + 20. So the shortest path changes to the other path with weight as 45.
The Minimum Spanning Tree doesn't change. Remember the Kruskal's algorithm where we sort the edges first. If we increase all weights, then order of edges won't change.
