2
$\begingroup$

The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"

Corollary 24.3

Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$ and a weight function $w: E \to \mathbb{R}$. Then, for each vertex $v > \in V$, there is a path from $s$ to $v$ if and only if BELLMAN-FORD terminates with $v.d < \infty$ when it is run on $G$.

I have an intuition for the corollary and would formulate its proof as following:

$\rightarrow$: Suppose there are paths from $s$ to $v$, we call the shortest path $p$. The path $p$ is shortest and therefore simple and hence has at most $|V| - 1$ edges. Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can concluse, that $v.d < \infty$ after the algorithm terminates.

Another argument may also include the "Path-relaxation property", which states $v.d = \delta(s, v) < \infty$ after relaxations of all edges of $p$.

$\leftarrow$: Suppose there is no path from $s$ to $v$ but Bellman-Ford terminates with $v.d < \infty$. This would be a contradiction with "No-path property", which states $v.d = \delta(s, v) = \infty$.

I am self-studying the book and there is a lack of feedbacks from tutor, so my question is: would my proof be sufficient in this case?

$\endgroup$
0
$\begingroup$

I think your proof is correct, but there are 2 things that I would like to comment:

  1. I think that when you are proving the $\rightarrow$ direction and you say:

"Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can conclude, that $v.d < \infty$ after the algorithm terminates."

there is an assumption that a call to RELAX will necessarily decrease $v.d$. But this is not necessarily true, as a call to RELAX can leave $v.d$ untouched. So, you would need to prove that in BELLMAN-FORD there would be a call to RELAX that necessarily decreases $v.d$. The alternative argument you are proposing (use the "Path-relaxation property") would work fine here, though.

  1. Since this is a corollary, I think the authors expected you to use the previous Lemma to solve it (of course, solving it via a different reasoning is ok too). In this case, we have Lemma 24.2:

Lemma 24.2 Let $G = (V, E)$ be a weighted, directed graph with source $s$ and weight function $w: E \rightarrow \mathbb{R}$, and assume that $G$ contains no negative-weight cycles that are reachable from $s$. Then, after the $|V| - 1$ iterations of the for loop of lines 2-4 of BELLMAN-FORD, we have $v.d = \delta(s, v)$ for all vertices that are reachable from $s$.

We can use it to prove the corollary:

$\rightarrow$: If there is a path from $s$ to $v$, by Lemma 24.2, we have $v.d = \delta(s, v)$, where $\delta(s, v)$ (the shortest path weight from $s$ to $v$) is less than $\infty$ since there is a path.

$\leftarrow$: If BELLMAN-FORD terminates with $v.d < \infty$ when it is run on $G$, by Lemma 24.2 we have that $\delta(s, v) = v.d < \infty$, which by definition of $\delta$ means that there is a path from $s$ to $v$.

$\endgroup$

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.