0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?! $\endgroup$ – jen007 Oct 31 '17 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.