World's most popular travel blog for travel bloggers.

[Answers] finding shortest negative cycle

, , No Comments
Problem Detail: 

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?

Asked By : Nikhil

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback