1,168 views
5 votes
5 votes

2 Answers

Best answer
5 votes
5 votes

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.

selected by
4 votes
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)

Related questions

1 votes
1 votes
3 answers
1
Rakesh K asked Nov 27, 2016
3,087 views
1 votes
1 votes
1 answer
2
jenny101 asked Oct 26, 2016
562 views
1 votes
1 votes
3 answers
3
3 votes
3 votes
2 answers
4
dd asked Dec 6, 2016
2,597 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...