“If every edge weight is increased by the same value” it simply means take any
constant C and add it to every edge that is there in the graph.
Why the MST will not change ?
PROOF:
MST simply means connecting n vertices using n-1 edges, keeping the sum of edge
weights as low as possible. So basically it reduces to a equation.
w1 + w2 + w3 + . . . . . . = m (previous MST)
W1 + W2 + W3 + . . . . . = M (New MST after adding constant weight)
we need to show that all the new edges maps exactly with old edges.
Considering kruskal’s algorithm, first we select the edge with least weight,
check for cycle and if everything seems good we add it to our MST and repeat,
increasing the weights on every edge will have no change in the
working of the algorithm, as the comparison based selection criteria
remains unaffected, same goes for Prim’s algo. also,
hence we are bound to get the same MST.
The Q part is wrong as we can easily think of a counter case for this.
We are using 2 as our constant weight.
The shortest path between A and E has been changed.