726 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

2 Answers

Best answer
8 votes
8 votes
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
1 votes
1 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
Answer:

No related questions found