# 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? – Yuval Filmus Mar 23 '16 at 18:51

## 1 Answer

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

• But Floyd–Warshall calculate the least weight of a walk only with the vertices {1,2,...,ℓ}, not the least weight of a walk with length ℓ. – Tomer Wolberg Jan 5 at 18:39
• You’re right, I meant some other algorithm. Perhaps Bellman-Ford? – Yuval Filmus Jan 5 at 18:46
• You can use Bellman Ford but you would need to run it from each vertex. – Tomer Wolberg Jan 6 at 16:04