The Gateway to Computer Science Excellence

+4 votes

+1

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.

+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.

+4 votes

Consider above graph,

**S1)**

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

**S2)**

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)**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,302 answers

198,306 comments

105,008 users