First time here? Checkout the FAQ!
+4 votes

asked in Algorithms by Active (1.4k points)   | 99 views
C, 1st statement false because if distance b/w  s-a is 1, a-b=1, b-t=1 & s-t=4; So shortest distance is s-a-b-t= 3; & if we add 1 in every edge so s-a-b-t=6 & s-t=5 .In this case shortest path is change.          2nd statement is true; take same data now double each edge so new distance s-a-b-t=6 & s-t=8; So shortest distance remain same.

2 Answers

+5 votes
Best answer

By using counter Example:

Here shortest path from s TO t is A to B and B to D. Let's increase edge weight of each edge by 3. Now the shortes path from s To t is A to D that is 7. So S1 is false.

if we multiply edge weights with same number the edge weights are increased in same ratio so No change in path but total weight has been changed.

So ans is option C.


answered by Veteran (22.8k points)  
selected by
Nice explanation @Gabbar..
+3 votes


Consider above graph,


Now suppose shortest path from S to A was S-B and then B-A. shortest path length = SB + BA = 5+5 =10

Now if we increase weight of each edge by 1, then new shortest path will be

shortest path length = min (SB + BA, SA)= min(6+6,11) =11

that means shortest path has changed. So S1 is wrong


Now even if we double the edge weight shortest path remains the same

shortest path length = min(SB + BA, SA) = min(10+10,20) = 20

that means shortest path is still S-B and then B-A

So S2 is correct

Hence answer should be C)

answered by Boss (7.8k points)  

Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1148 Points

  8. Debashish Deka

    1112 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    392 Points

23,361 questions
30,068 answers
28,385 users