# finding shortest negative cycle

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

• Do you consider a cycle of length 2 a simple cycle? Mar 23 '16 at 18:51

You can use dynamic programming (in this case, known as the Floyd–Warshall algorithm) to calculate the least weight of a walk of length $\ell$ from $x$ to $y$, for all vertices $x,y$ and $\ell \geq 0$. The first $\ell$ (if any) such that this weight is negative is the length of the shortest negative cycle. (This breaks if there are bidirectional negative edges, unless you consider them as simple cycles.)