4 votes

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)?$

- $2$
- $-1$
- $0$
- $1$

1 vote

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.