20
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ link is broken. $\endgroup$ – human.js Dec 12 '15 at 5:44
  • $\begingroup$ The linked PDF can be found here. $\endgroup$ – Paya Mar 1 '17 at 23:15
  • $\begingroup$ I just used Prof. Huang's idea, but I don't understand why he adds both a new source node and a new target (s' and t'). It seemed to me that a new source node, connected to all existing vertices by an edge of whatever length, would turn up all the cycles. $\endgroup$ – AbuNassar Nov 10 '17 at 0:55
0
$\begingroup$

Your example does not contradict your idea. Indeed you have found a negative cycle. I think the idea your example illustrates is that the source vertex might not be a node in the negative cycle.

$\endgroup$

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.