Let G = (V, E) be a directed, weighted graph with weight function w: E -- R. For some function f: V

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2020 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2020 question covers Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2020 Algorithm question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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) in 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, _______.'

Accepted Answer

Correct Answer: (A)Concept -- Johnson's Algorithm and Reweighting: The reweighting function w'(u,v) = w(u,v) + f(u) - f(v) is exactly the technique used in Johnson's algorithm. For any path from s to t: sum of w'(edges) = sum of [w(u,v) + f(u) - f(v)] = sum_w + f(s) - f(t). Since f(s) - f(t) is constant for any fixed s, t pair regardless of the path taken, any shortest path under w is also a shortest path under w'. This works for ANY function f -- the relative ordering of path weights is preserved. However, option A describes the necessary and sufficient condition when considering ALL pairs of vertices and ensuring non-negative edge weights (needed for Dijkstra). When f(u) is the shortest distance from a newly added source s to u, the reweighting guarantees non-negative edge weights while preserving shortest paths. This is the standard formulation in Johnson's algorithm.

Master GATE-CS with Our Test Series

More Questions from Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)

Frequently Asked Questions