Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it.

How can I get the actual path $v1, v2, \ldots vk, v1$ of the cycle?

After applying the standard algorithm we already did $n-1$ iterations and no further improvement should be possible. If we can still lower the distance to a node, a negative cycle exists.

My idea is: Since we know the edge that can still improve the path and we know the predecessor of each node, we can trace our way back from that edge until we meet it again. Now we should have our cycle.

Sadly, I did not find any paper that tells me if this is correct. So, does it actually work like that?

Edit: This example proofs that my idea is wrong. Given the following graph, we run Bellman-Ford from node $1$.

enter image description here

We process edges in the order $a, b, c, d$. After $n-1$ iterations we get node distances:
$1: -5$
$2: -30$
$3: -15$

and parent table:
$1$ has parent $3$
$2$ has parent $3$
$3$ has parent $2$

Now, doing the $n$th iteration we see that the distance of node $1$ can still be improved using edge $a$. So we know that a negative cycle exists and $a$ is part of it.

But, by tracing our way back through the parent table, we get stuck in another negative cycle $c, d$ and never meet $a$ again.

How can we solve this problem?

share|improve this question

1 Answer 1

up vote 6 down vote accepted

You are right for the most part. Just one more addition. When you go back the predecessor chain when trying to find the cycle, you stop when you either reach the starting vertex $v_1$ or any other vertex that has already been seen in the predecessor chain that you have seen so far. Basically, you stop and output vertices whenever you detect a cycle when going backwards using the predecessors.

As for papers, a simple Google search yields Xiuzhen Huang: Negative-Weight Cycle Algorithms. As a bonus, they also list another algorithm for finding negative weight cycles that are not reachable from the source vertex $s$.

share|improve this answer

Your Answer

 
discard

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

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