# Questions on shortest path and minimum spanning tree

T/F Questions

1. Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False

I think this should be True, as Dijkstra's Algorithm sums the paths from source to each vertex. If every edge weight is increased by a constant, then nothing should be changed if all edges are positive. If some edges are negatives, then I don't know if Dijkstra's Algorithm still applies here.

1. Adding a constant to every edge weight does not change the solution to the MST problem. (I don't have the solution for this)

I think this is True for the same reason above.

Can someone confirm on this?

You are wrong on the first one and right on the second one (but for the wrong reason).

To see that (1) is false, just observe that there exists a constant $c$ such that adding $c$ to all weights turns the weighted minimum distance problem into the unweighted one.

On the other hand, (2) is true because every spanning tree contains has exactly $|V|-1$ edges, therefore adding $c$ to all weights adds $c(|V|-1)$ to the total cost of each spanning tree.

• Can you elaborate on "adding c to all weights turns the weighted min distance problem into the unweighted one"? If I have weights w_1, w_2, w_3, ...w_n, adding c will turn weights into w_1 + c, w_2 + c, w_3 + c.... w_n + c. I think the problem is still a minimum distance problem as all the weights are different and enlarged?! – jen007 Oct 31 '17 at 23:23

From @quicksort answer it should be clear that min spanning tree remains same. Just to understand why it is false for the shortest path problem, consider the following counter-example. Let a graph contain only the following 2 paths-: $S-W-T$ and $S-U_1-U_2-U_3-T$. Let the weights of the edges be -: $S-W : 2\\ W-T : 2\\ S-U1 : 1\\ U1-U2 : 1\\ U2-T : 1$

Now the shortest S-T path is S-U1-U2-T. Now add a weight of 5 to all edges, and convince yourself the new shortest path will be S-W-T