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?

  • 1
    $\begingroup$ Do you consider a cycle of length 2 a simple cycle? $\endgroup$ Commented Mar 23, 2016 at 18:51

1 Answer 1


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

  • $\begingroup$ 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 ℓ. $\endgroup$ Commented Jan 5, 2019 at 18:39
  • $\begingroup$ You’re right, I meant some other algorithm. Perhaps Bellman-Ford? $\endgroup$ Commented Jan 5, 2019 at 18:46
  • $\begingroup$ You can use Bellman Ford but you would need to run it from each vertex. $\endgroup$ Commented Jan 6, 2019 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.