1
$\begingroup$

I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.

(Elementary Cycle: A cycle is elementary if no vertex but the first and last appears twice.)

But I want to find ALL elementary negative weight cycles. Even taking each vertex as the source will not always get ALL negative weight cycles.

Take this graph for example:

enter image description here

With Bellman-Ford, starting from any vertex, I can only get one cycle "U→H→U".

The cycle "U→S→U" is always missing.

Is there any algorithm with which I can find all negative weight cycles reliably?

$\endgroup$
  • $\begingroup$ (I needed three attempts to understand $A$ until I concluded that you probably want to emphasise exactly one.) If there is more than one negative weight cycle, what is the elementary circuit? $\endgroup$ – greybeard Oct 4 at 21:08
  • $\begingroup$ @greybeard Thanks for your comments. How about this version? Is it more clear now? $\endgroup$ – Long Bu Oct 5 at 1:21
  • $\begingroup$ I do think so - let me try and give a hand. $\endgroup$ – greybeard Oct 5 at 5:44
  • $\begingroup$ You might get a lot of cycles: for example in a complete graph on $n$ vertices, where all edge weights are negative, you would get something like $n!$ elementary cycles. Do you want to impose some kind of disjointness condition on the output cycles? $\endgroup$ – Joppy Oct 6 at 11:03
0
$\begingroup$

My current strategy is:

  1. first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library.
  2. sum all the weights of edges in each cycle and then check if the sum is negative.
| cite | improve this answer | |
$\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.