In a weighted graph, assume that the shortest path from a source ‘s’ to a destination ‘t’ is correctly calculated using a shortest path algorithm. Is the following statement true?
If we increase weight of every edge by 1, the shortest path always remains same.
(A) Yes
(B) No
Answer: (B)
Explanation: See the following counterexample.
There are 4 edges s-a, a-b, b-t and s-t of wights 1, 1, 1 and 4 respectively. The shortest path from s to t is s-a, a-b, b-t. IF we increase weight of every edge by 1, the shortest path changes to s-t.
1 1 1 s-----a-----b-----t \ / \ / \______/ 4
Read full article from Algorithms | Graph Shortest Paths | Question 8 - GeeksQuiz
No comments:
Post a Comment