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

Answer 3

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.

Answer 4

$\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:-

$\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.