# how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?

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:

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?

• (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? – greybeard Oct 4 at 21:08
• @greybeard Thanks for your comments. How about this version? Is it more clear now? – Long Bu Oct 5 at 1:21
• I do think so - let me try and give a hand. – greybeard Oct 5 at 5:44
• 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? – Joppy Oct 6 at 11:03