0 votes 0 votes Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False Algorithms algorithms minimum-spanning-tree + – VS asked Dec 8, 2017 VS 3.8k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments VS commented Dec 8, 2017 reply Follow Share @joshi_nitish 1) Adding a constant value to each of the edges can change the shortest path. TRUE 2) Can multiplying each edge by a constant value(c ) change the shortest path ? I think no ! Only cost of the shortest path will be changed i.e = c * old shortest path value 3) Adding a constant value to each of the edges can change the MST. FALSE Only cost of the MST will be changed i.e = c * (#vertices -1) + Old cost 4) Multiplying each edge by a constant value(c) change the MST. FALSE Only cost of the MST will be changed i.e = c * Old cost Can you verify ? 3 votes 3 votes joshi_nitish commented Dec 8, 2017 reply Follow Share @VS yes, all correct. 1 votes 1 votes shashank023 commented Jan 14, 2021 reply Follow Share Can multiplying each edge by a constant value(c ) change the shortest path ? Multiplying each edge by a constant value(c) change the MST Both Yes in case of -ve constant. Correct me if I’m wrong. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes YES.....BUT MST WILL REMAIN SAME. NEW COST=OLD COST*X X=POSITIVE NO. Priyanka Agarwal answered Dec 8, 2017 Priyanka Agarwal comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 25, 2017 reply Follow Share To add: In case negative number is multiplied, MST may change. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes only you will get change in shortest path value according to your multiplicative value remains will be same air1ankit answered Dec 8, 2017 air1ankit comment Share Follow See all 0 reply Please log in or register to add a comment.