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 Algorithms graph-algorithms shortest-path graph-theory + – dd asked Dec 6, 2016 dd 2.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply mohit chawla commented Dec 6, 2016 i edited by mohit chawla Dec 6, 2016 reply Follow Share false. 0 votes 0 votes Kaluti commented Jan 20, 2018 reply Follow Share yes it would be false 0 votes 0 votes Please log in or register to add a comment.
Best answer 12 votes 12 votes Check the figure !! Kapil answered Dec 6, 2016 • selected Dec 6, 2016 by dd Kapil comment Share Follow See all 2 Comments See all 2 2 Comments reply mohit chawla commented Dec 6, 2016 reply Follow Share Thank you @kapil for providing a very clean expalnation. 1 votes 1 votes Shubhanshu commented Mar 13, 2017 reply Follow Share nice explanation!!! 1 votes 1 votes Please log in or register to add a comment.
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. pradeepchaudhary answered Nov 28, 2018 pradeepchaudhary comment Share Follow See all 0 reply Please log in or register to add a comment.
