in Algorithms
332 views
3 votes
3 votes

Consider the below statements:

  1. Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
  2. Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem.
  1. 1 is FALSE 2 is TRUE
  2. 1 is TRUE 2 is FALSE
  3. Both 1 and 2 are TRUE
  4. Both 1 and 2 are FALSE
in Algorithms
by
332 views

3 Comments

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

@Arjun sir here asking mst only so when duplicate is present then it can be change 

1
1
yes, you are correct. I have updated the answer.
0
0

2 Answers

8 votes
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.
selected by
by

4 Comments

sir , here solution means what ,sets of edges included in MST or total cost of edges included??
0
0
MST means tree should also be part of solution.
0
0
Here solution means Path Am i r8?

why not value too??how to understand such Q?
0
0
0 votes
0 votes

Facts:-

  1. Adding a constant to every edge weight may change the solution to the single-source shortest-paths problem.
     
  2. Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem.
     
  3. Multiplying a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
     
  4. 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