Questions on shortest path and minimum spanning tree

Question

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.

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

Answer 1

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.

Answer 2

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