1
$\begingroup$

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 :

enter image description here

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.

$\endgroup$
  • $\begingroup$ If the algorithm decides to use any cycle, it is negative because the objective is to discover the path with the lowest cost. In other words, the algorithm would never select (c, a, b, c, d) unless (c, a, b) was cheaper than just (c). The alternative path being (c, d). $\endgroup$ – Michael Zedeler Apr 23 '13 at 21:10
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I might confuse with what I'm trying to prove. I read the document in the post. I understand that in case the algorithm return "Negative Cycle" then there must be a negative cycle in the parent pointer. As far as I understood I though I should prove that if there is a cycle in the parent pointer it must be negative no matter if the algorithm returns "Negative cycle" or not. So I can prove this only if I know that the algorithm found a "Negative Cycle", right? $\endgroup$ – SyndicatorBBB Apr 22 '13 at 11:54
  • $\begingroup$ The algorithm says it found a 'negative cycle', if it finds a 'cycle' in parent pointers. The proof given there is to show that whenever the algorithm finds a cycle in parent pointers, it must correspond to a negative cycle in the graph (and that all negative cycles can be found this way). I will edit the answer and add an outline of this proof. $\endgroup$ – polkjh Apr 23 '13 at 13:43
  • $\begingroup$ Wow, thank you very much! I appreciate your help and time to help me understand the problem/solution. $\endgroup$ – SyndicatorBBB Apr 24 '13 at 17:11

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.