Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford algorithm.

The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from $V$ that $u$ is its parent until we close a cycle.

I'm having little problem proving this. I want to prove now that no matter when I stop the algorithm - if $p[v] = u$ always $d[v]\le d[u]+w(u,v)$ and to prove that a cycle in parent pointer is necessarily a negative cycle.

share|cite|improve this question
Have a look at this. – Paresh Dec 23 '12 at 23:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.