2,595 views
3 votes
3 votes

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 shortest path from s to t. T/F

2 Answers

Best answer
12 votes
12 votes

Check the figure !!

selected by
0 votes
0 votes

Absolutely False.....

Think in the terms of number of edges involved in the path.....More the number of edges higher the increase in the path. So definitely  it is possible that some other path with less number of edges became the shortest path.

Related questions

1 votes
1 votes
3 answers
1
1 votes
1 votes
3 answers
2
Rakesh K asked Nov 27, 2016
3,086 views
5 votes
5 votes
2 answers
3
jenny101 asked Oct 26, 2016
1,168 views
1 votes
1 votes
1 answer
4
jenny101 asked Oct 26, 2016
562 views