### The_dreamer_'s blog

By The_dreamer_, history, 4 months ago, Please help me with this problem: Given an undirected weighted graph have n vertices and m edges (n <= 1000, m <= 10000). How to check if there exists a simple cycle have total weight >= 0. Thanks for your help. Comments (8)
 » You can multiply each edge weight by $-1$. Then use Bellman Ford's algorithm to find a negative cycle which iirc works in $O(n^2 + n \cdot m)$.
•  » » But as far as I know, it can only be used for directed graph. When use it in undirected graph, this algorithm can go on a loop in a negative weighted edge (cycle of length 2) but it not simple cycle.
•  » » » Not sure. There's another approach you can try. It has an $O(m^2)$ complexity so not sure if it will pass. For eaxh edge from node $a$ to node $b$ with weight $w$, "remove" that edge, then find the shortest distance between $a$ and $b$ (assuming there is indeed a path between these after removing the edge). Let the distance found be $p$. You have a cycle with weight $p+w$.
•  » » » » But how can we find the shortest distance between a and b ? It still can go on a loop in a negative weighted edge.
 » Can someone help me please. I still can't solve this problem.
•  » » Sorry I forgot to reply back. You can use modified Bellman Ford's: keep track of the node used to relax the distance for every node, this way you can avoid 2 node cycles.