1
$\begingroup$

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.

enter image description here

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – FrankW Oct 8 '14 at 6:28
  • 1
    $\begingroup$ Assume the opposite, i.e. the difference is greater than one. What can you conclude? $\endgroup$ – Raphael Oct 8 '14 at 7:48
  • $\begingroup$ What is "intro to algorithms"; the book by CLRS? $\endgroup$ – Raphael Oct 8 '14 at 12:19
  • $\begingroup$ I don't think the proof is correct at all - it merely restates the theorem. $\endgroup$ – reinierpost Oct 8 '14 at 15:28
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Oct 8 '14 at 8:04
  • 2
    $\begingroup$ @DavidRicherby Given the time difference between posting the two answers, they have likely started typing before your answer appeared. $\endgroup$ – FrankW Oct 8 '14 at 8:13
  • $\begingroup$ 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'. $\endgroup$ – reinierpost Oct 8 '14 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Amir Oct 8 '14 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.