Computer Sciences > Gate 2020 > 1
Let G=(V,E) be a directed, weighted graph with weight function w:E→R.
For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as w(u,v)+f(u)−f(v).
Which one of the options completes the following sentence so that it is TRUE ? “The shortest paths in G under w are shortest paths under w′ too, _________”.
For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as w(u,v)+f(u)−f(v).
Which one of the options completes the following sentence so that it is TRUE ? “The shortest paths in G under w are shortest paths under w′ too, _________”.
Explanation
Correct : a
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.