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$
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$
  • 1
    $\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
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$
0
$\begingroup$

This answer on stackoverflow has an example of why 1 is false.

https://stackoverflow.com/questions/10790909/adding-weights-to-all-edges-of-graph-change-in-spanning-tree-and-shortest-path

Quoting from the above:

Consider a graph with 3 vertices (A,B,C), with the following edges:

A-B = 1
A-C = 0
C-B = 0

The shortest weighted path between A and B is A-C-B. If you add 2 to all the weights, your shortest path becomes A-B.

$\endgroup$
0
$\begingroup$

$\mathbf 1.$

Say there are two paths from node A to node B.

Path1 has 4 edges.

Path2 has 2 edges.

An overall increase in edge weight by x increases,

the cost of Path1 by 4x.

the cost of Path2 by 2x.

If Path 1 was the optimum path found by Dijkstra then in order for it to remain the optimum path even after the increase.

$Cost_{Path1} + 4x < Cost_{Path2} + 2x$

or

$2x < Cost_{Path2}-Cost_{Path1}$

For $x= \frac{Cost_{Path2}-Cost_{Path1}}{2} $ this is no longer valid.

Consider the given example:- Example

$\mathbf 2.$

Suppose there are two selections of edges for a MST.

$S_1$ with cost $Cost_{S1}$ and edges $E$

and

$S_2$ with cost $Cost_{S2}$ and edges $E$

Note that both have the same number of edges since MST is a tree and has $Edges = Vertices -1$

If $S_1$ is the answer to the MST problem then,

$Cost_{S1}<Cost_{S2}$

An increase in edge weight by $x$ would result in

$Cost_{S1} + E*x <Cost_{S2} +E*x$

which is the same.

Thus no value of $x$ changes the answer to the MST problem.

$\endgroup$

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.