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.

• +21

 » 4 months ago, # |   +10 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)$.
•  » » 4 months ago, # ^ |   +13 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.
•  » » » 4 months ago, # ^ |   0 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$.
•  » » » » 4 months ago, # ^ |   0 But how can we find the shortest distance between a and b ? It still can go on a loop in a negative weighted edge.
 » 4 months ago, # |   0 Can someone help me please. I still can't solve this problem.
•  » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   0 problem link??
 » 4 months ago, # |   0 I think you can use Bellman Ford's algorithm but with vertices {vertex, last edge}, and then you update distance only if new edge is not equal to the last edge used. I think it will still be O(m^2) because every edge creates only 2 new vertices.