[Solved]: Bellman-Ford parent pointer (?) negative cycle

Problem Detail: 

First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof itself.

So after some search in the site I found the following question : Bellman-Ford algorthm and negative cycle proof.

The guy is trying to understand how to prove that a cycle in parent pointer is necessarily a negative cycle.

My question is very basic and isn't duplicate, I just couldn't find anything in the document on the related question which answers my question.

What does it mean a cycle in the parent pointer? I mean I could a graph whereas the cycle in the parent pointer isn't a negative cycle... I don't understand why It must be a negative cycle.

See an example of a graph I have in mind :

Now suppose the first node we start with is (a) and suppose the we travling the edges in the following order: ab,bc,cd.

and here we goes, we have a cycle in the parent pointer, and as far as I understand that is (c) becuase it is the parent of (d) and yet the cycle isn't negative cycle.

Asked By : SyndicatorBBB

Answered By : polkjh

In the notation here, a vertex $v$ is called a parent pointer of a vertex $u$, if a shortest path to $u$, found so far in the algorithm, has $v$ preceding $u$. So in the graph above, starting at $a$ and moving to $b,c,d$ in that order, the parent pointers are $a,b,c$ respectively for $b,c,d$.

We say there is a loop in parent pointers if we have vertices $v_1,v_2, \ldots ,v_n$ such that $v_i$ is a parent of $v_{i+1}$ and $v_n$ is a parent of $v_1$. Notice that this is not happening in the earlier example. But if we change the weight of edge $(c,a)$ to $-3$, then we have $a$ as parent of $b$, $b$ parent of $c$ and $c$ as parent of $a$, forming a loop in parent pointers, indicating a negative cycle.

Proof for why this finds negative cycles is given in the document referred in that earlier post

Edit:

Suppose we have found a cycle $v_1,v_2,\ldots , v_n$ in parent pointers ($v_i$ is parent of $v_{i+1}$ and $v_n$ is parent of $v_1$). Let $P(v)$ denote the shortest path length obtained to vertex $v$ so far. Then, as $v_i$ is parent of $v_{i+1}$, we get $P(v_{i+1}) = P(v_i) + w(v_i,v_{i+1})$, where $w(u,v)$ is weight of the edge from $u$ to $v$. So $P(v_n) = P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}$. We have reached $v_n$ so far and now looking at its neighbour $v_1$. And $v_n$ is made parent of $v_1$. Which means the shortest path length to $v_1$ ($P(v_1)$) found so far is bigger than the path coming from $v_n$. That is, $P(v_1) > P(v_n) + w(v_n,v_1)$. Hence,

$$ P(v_1) > P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})} $$ $$ 0 > \sum_{i=1}^{n-1} {w(v_i,v_{i+1})} $$

So any cycle in parent pointers corresponds to a negative cycle in the graph.

Note that this is only one half of the proof. We still need to show the converse (whenever there is a negative cycle in the graph, we will get a cycle in parent pointers).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11428

 Ask a Question

 Download Related Notes/Documents