in Algorithms
358 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
358 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

6 Comments

But @Arjun sir, in the question it is wriiten that adding a constant to every edge weight does not change the solution to the minimum spanning tree problem. That means if initially graph is not having distinct edges then in that case too multiple solution for mst is possible and these solutions will match with the new solution that we obtained after adding constants to edges.

1
1
Yes, It depends on the wordings in question. The output of the algorithm can change. But given the solution, it is still valid. A is the better answer as per the given question.
1
1
Sir, I was also thinking A) but previously answer was given as D) that's why.
1
1
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