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:
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?