GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
119 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 (50.5k points)   | 119 views
false.

1 Answer

+9 votes
Best answer

Check the figure !!

answered by Veteran (47.6k points)  
selected by
Thank you @kapil for providing a very clean expalnation.
nice explanation!!!


Top Users Jul 2017
  1. Bikram

    4386 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1686 Points

  5. Arjun

    1340 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1080 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    732 Points


24,031 questions
30,983 answers
70,430 comments
29,358 users