[Solved]: Finding all vertices on negative cycles

Problem Detail: 

Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a way to do it faster than Floyd-Warshall's $O(|V|^3)$?

Asked By : tempestadept

Answered By : D.W.

I was not able to turn up any better algorithm in my research.

In practice, you could improve the running time for many graphs by first decomposing the graph into strongly connected components, then running Floyd-Warshall on each strongly connected component. This does not improve the worst-case complexity (since in the worst case the entire graph could form one large strongly connected component), but it might help on many graphs you're likely to run into in practice.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12243