576 views

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$  For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$

1. $2$
2. $-1$
3. $0$
4. $1$

### 1 comment

d[u] => shortest path from s to u

d[v] => shortest path from s to v

(1) d[u] $\leqslant$ d[v] + 1 ( if d[u] > d[v] + 1 than d[u] can’t be shortest path from s to u )

same way

(2) d[v] $\leqslant$ d[u] + 1 ( if d[v] > d[u] + 1 than d[v] can’t be shortest path form s to v)

use 1st eneuqlity d[u] – d[v] $\leqslant$ 1

use 2nd eneuqality d[u] – d[v] $\geqslant$ -1

so from above two enquality  -1  $\leqslant$ d[u] – d[v] $\leqslant$  1

So d[u] – d[v] = 2 is not possible

Here $d(u)=2$  and $d(v) = 1$ so $d(u) - d(v) = 2-1 =1$ so option $B$ eliminated.

here $d(u) = d(v) = 1$ so $d(u) - d(v) = 0$ so option $C$ eliminated.

Here $d(u)=1$  and $d(v) = 2$ so $d(u) - d(v) = 1-2 =-1$ so option $D$ eliminated.

If you look at the above graphs then you would realize that we are just either calculating the shortest path of $s$ from either vertex $v$ or $u$(whichever is the shortest) and then just adding $1$ since both $u$ and $v$ are adjacent to each other so shortest path would increase by just $1$ edge distance.

Hence the difference between $d(u) - d(v)$ can never be greater than $1$.

So Option $A$ is the correct answer.

by
max difference between d(u) and d(v) is 1. Bcz if d(u) not equal to d(v), then d(u)=d(v)+1( for edge u-v). As this is undirected graph, we do not need to think about direction. hence option A is the correct answer.
by

1 vote