Getting negative cycle using Bellman Ford

Question Detail: 

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

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?

Asked By : Patrick Schmidt

Best Answer from StackOverflow

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

Answered By : Paresh

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