I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and also needed some care to prevent the algorithm from ping ponging between a pair of vertices adjacent to a negative edge.  
Another thing about using the Bellman-Ford algorithm for detecting negative cycles is that it requires $O(n^3)$ preprocessing before it allows the detection of negative cycles, not to mention that experiments suggest, that it gets "stuck" in a single such cycle.  

Now my idea would be to 

> - calculate the graph's MST 

> - calculate the all pairs shortest path distances of the MST   

> - report the existence of a negative cycle, if an edge can be found, for which $(u,v)\in E\setminus\{ E\cap MST\}$ and $dist_{MST}(u,v)+w(v,u) \lt 0$ holds. 

the complexity would be $O(n^2)$ instead of $O(n^3)$, but:

**Questions**   

- would the algorithm sketched above correctly report the existence of negative cycles, resp. in which cases will it fail?  

- is the set of edges that are not in the MST, but whose union with the edges on the shortest MST-path between their adjacent vertices is a negative cycle, represent a negative-cycle transversal of the graph?  

**Addendum**  
In the abstract of this [article](http://link.springer.com/chapter/10.1007/978-3-642-02270-8_7?no-access=true) it is stated, that the problem of detecting negative cost cycles in undirected graphs (UNCCD problem) is "*significantly harder than the corresponding problem in directed graphs*" and the complexities of different algorithms are given, ranging from $O(n^{2.75}\log n)$ to $O(n^6)$