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
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
