quetion is about mst not cost of mst...so it will be change.

Dark Mode

Bikram
asked
in Algorithms
Oct 4, 2016

358 views
3 votes

Consider the below statements:

- Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
- Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem.

- 1 is FALSE 2 is TRUE
- 1 is TRUE 2 is FALSE
- Both 1 and 2 are TRUE
- Both 1 and 2 are FALSE

8 votes

Best answer

Consider

A--B--C, where AB weight = 2, BC wight = 2 and AC weight = 5. Shortest path from A--C is via B with weight 4. Now if we add a constant weight say 3 to each of them, shortest path becomes A--C with weight 8.

If edge weights are distinct MST remains same if a constant weight is added to all edges. Otherwise the output of a MSTalgorithm can change as multiple solutions are possible for the MST problem. Still the old solution is valid (correct) and hence the statement is true.

A--B--C, where AB weight = 2, BC wight = 2 and AC weight = 5. Shortest path from A--C is via B with weight 4. Now if we add a constant weight say 3 to each of them, shortest path becomes A--C with weight 8.

If edge weights are distinct MST remains same if a constant weight is added to all edges. Otherwise the output of a MSTalgorithm can change as multiple solutions are possible for the MST problem. Still the old solution is valid (correct) and hence the statement is true.

0 votes

Facts:-

- Adding a constant to every edge weight
**may****change**the solution to the single-source shortest-paths problem.

- Adding a constant to every edge weight
**does not change**the solution to the minimum spanning tree problem.

- Multiplying a constant to every edge weight
**does not****change**the solution to the single-source shortest-paths problem.

- Multiplying a constant to every edge weight
**does not change**the solution to the minimum spanning tree problem.

**Option A**

The intuition behind them:-

- Shortest path between two vertices can contain any number of edges. When you add a constant factor to every edge, depending on how many edges are there in your shortest path, the addition might not be uniform.

Say, a path between A to B has 10 edges each of weight 1. Another path between A and B has 6 edges each of weight 2.**Former path is shorter**.

Now, add 9999 to every edge. In the former path this means adding 9999 ten times. In the latter path, it means adding 9999 six times.**Now, latter path is shorter**.

- In case of MST, we consider edges individually, not their combinations like we did above. So, any addition or multiplication would affect each edge
*uniformly*