The GATE Grind

GATE 2020 CS – Question 50

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

Let $G=(V,E)$ be a directed, weighted graph with weight function $w:E\to\mathbb{R}$. For some function $f:V\to\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. for every $f:V\to\mathbb{R}$
  2. if and only if $\forall u\in V$, $f(u)$ is positive
  3. if and only if $\forall u\in V$, $f(u)$ is negative
  4. 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 this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) for every $f:V\to\mathbb{R}$

Explanation

For any path from $s$ to $t$ the reweighted length is $w(p)+f(s)-f(t)$. The extra term depends only on the endpoints, so the ordering of paths between the same endpoints is unchanged for every $f$ (this is Johnson's reweighting).