# Proving that shortest path distance of adjacent nodes can't differ by more than one

Could someone explain this proof to the following question?

Lemma 22.1 from intro to algorithms

Let $$G=(V,E)$$ be a directed or undirected graph, and let $$s\in V$$ be any vertex. Then, for any edge $$(u,v)\in E$$,

$$\mathrm{dist}(s,v)\leq \mathrm{dist}(s,u)+1\,.$$ Proof. If $$u$$ is reachable from $$s$$, then so is $$v$$. In this case, the shortest path from $$s$$ to $$v$$ cannot be longer than the shortest path from $$s$$ to $$u$$ followed by the edge $$(u,v)$$ and thus the inequality holds.

I drew this to visualize the problem but I don't see how what I drew is wrong and how the proof is correct.

If going from $$s$$ to $$u$$ has less vertices along that path than going from $$s$$ to $$v$$, than the shortest distance of $$s$$ to $$v$$ should be greater than going from $$s$$ to $$u$$ and $$s$$ to $$u$$ to $$v$$.

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Oct 8 '14 at 6:28
• Assume the opposite, i.e. the difference is greater than one. What can you conclude? – Raphael Oct 8 '14 at 7:48
• What is "intro to algorithms"; the book by CLRS? – Raphael Oct 8 '14 at 12:19
• I don't think the proof is correct at all - it merely restates the theorem. – reinierpost Oct 8 '14 at 15:28

## 2 Answers

I don't understand your diagram but the point is that, if there is a $x$–$y$ path of length $k$ then the distance from $x$ to $y$ cannot be bigger than $k$.

So, suppose the shortest path1 $P$ from $s$ to $v$ has length $k$. If that path includes $u$, then there is a path of length less than $k$ from $s$ to $u$. Since there is a path of length less than $k$, the distance from $u$ to $v$ is less than $k$, so it is less than or equal to $k+1$, as required. On the other hand, if $P$ does not include $u$, then $P$ followed by the edge $uv$ is a path from $s$ to $v$ of length $k+1$. Since there is a path of length $k+1$, the shortest path can't be longer than that, so the distance is at most $k+1$.

1 I should really say "a shortest path", since there can be multiple different paths, all of the same length.

Consider the shortest path between $s$ and $u$, and suppose it has $n$ edges. Then append one edge to the path, which is $(u,v)$. We get a path from $s$ to $v$, of length $n+1$.

By definition, the length of the shortest path between $s$ and $v$ is not greater than $n+1$, which is the length of some path between $s$ an $v$.

Makes sense?

• Didn't I already say all of that in my answer? Except that I was careful to deal with the case that $v$ is already on the shortest $s$-$u$ path $P$ since, in that case, you can't add the edge $uv$ to the path $P$ and call it "a path between $s$ and $v$" since the "path" contains a cycle. – David Richerby Oct 8 '14 at 8:04
• @DavidRicherby Given the time difference between posting the two answers, they have likely started typing before your answer appeared. – FrankW Oct 8 '14 at 8:13
• I think this answer is clearer: it leaves out unnecessary detail. However, the question was not to come up with a proof but what is wrong with the given 'proof'. – reinierpost Oct 8 '14 at 15:30
• adding to the answer: the thing that's wrong with the drawing is the path between $s$ and $v$ of length $5$. This is obviously not the shortest path, because the path $s-u-v$ is of length $3$. And this is exactly what the lemma is about. – Amir Oct 8 '14 at 23:31