List all negative cycles in directed graph

3
votes

For a directed graph G(V,E) where it has negative weights, I searched some similar topics and it seems Bellmanford can detect negative cycles. But it stops once negative cycles found, so how can we list all negative cycles in this case?

Given thoughts on Eric Lippert's suggestion, I tried removing negative cycles once found from graph, but I feel this is not correct, why? because the graph changes after cycles are removed and there could be extra non-negative cycles in old graph but not gonna be found in new graph. Can someone please help clear my mind on this issue?

this can be implemented in either java or c# (i prefer c# though)

thanks

1
c#javaalgorithmgraph-algorithm
Looks like you don't need java tag.. – Soner Gönül
sorry, i was changing it, but you were quicker.. – ikel
Find a negative cycle. Remove it. Now search again. Repeat until you can no longer find a negative cycle. Now you've counted the negative cycles. – Eric Lippert
but that only track the count, right? i need the full path though – ikel
a cycle whose edges sum to a negative value in a directed graph – ikel

1 Answers

0
votes

Well, you certainly can't find them efficiently: consider the complete graph on n vertices with a weight of negative -1 on each edge. There are an exponential number of negative-weight cycles in this graph and as such it'd take exponential time to just write them all down!

If that doesn't deter you though, your best bet is to apply any old cycle finding algorithm, such as the ones in this question to find all cycles, and then just throw out those cycles with non-negative weight.