GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
83 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 shortest path from s to t. T/F

asked in Algorithms by Veteran (41.3k points)   | 83 views
false.

1 Answer

+9 votes
Best answer

Check the figure !!

answered by Veteran (42.3k points)  
selected by
Thank you @kapil for providing a very clean expalnation.

Related questions

0 votes
2 answers
1
+4 votes
2 answers
2
asked in Algorithms by jenny101 Active (1.3k points)   | 81 views
+2 votes
1 answer
3
asked in Algorithms by jenny101 Active (1.3k points)   | 67 views
Top Users Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,022 answers
59,696 comments
22,133 users