GATE CS 2020 (Forenoon) — Question 50

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMCQ2 marks · −2/3 if wrongMedium

Let \( G = (V, E) \) be a directed, weighted graph with weight function \( w : E \rightarrow \mathbb{R} \). For some function \( f : V \rightarrow \mathbb{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, ________".
  1. A
    for every \( f : V \rightarrow \mathbb{R} \)
  2. B
    if and only if \( \forall u \in V, f(u) \) is positive
  3. C
    if and only if \( \forall u \in V, f(u) \) is negative
  4. D
    if and only if \( f(u) \) is the distance from \( s \) to \( u \) in the graph obtained by adding a new vertex \( s \) to \( G \) and edges of zero weight from \( s \) to every vertex of \( G \)
Practise the full 2020-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group