Negative Weight Cycle Algorithm

Question

I was thinking about the algorithm of finding a negative weight cycle in a directed graph. The Problem is: we have a graph G(V,E), we need to find an efficient algorithm to find a cycle with negative weight. I understand the algorithm in this PDF document

Briefly, the algorithm is applying Bellman Ford algorithm by iterating |V|-1 times doing relaxations. Afterwards it checks if there is an edge that can be even relaxed more, then a negative weight cycle exists and we can trace it back by parent pointers and everything goes well, we find a negative weight cycle.

However, I was thinking of another algorithm of just using depth-first search (DFS) on the graph by keeping track of the sum so far of the distances you traversed, I mark all nodes white at the beginning and make them grey when I am searching a path, and mark them black when they are finished, that way I know that I find a cycle if and only if I find a visited node and it is grey (in my path) , not black which was already finished by the Depth-First search, and so for my algorithm, if I reach a grey node that has already been visited, I check what would it's update be (the new distance) and if it is lower than before, I know that I have a negative weight cycle and can trace it back.

Is my algorithm wrong? If so, can you find a counterexample ? If not can you help me prove it?

Thank You

Answer 1

Bellman Ford doesn't always work, the problem is its a single source shortest path algorithm, if the negative loop is not reachable from the source you pick, it fails. However a little change to Bellman Ford could help, instead of selecting a source vertex and initialise its distance to 0, we can initialise all the distance to 0 and then run Bellman Ford. This is equivalent to add a extra vertex s' which points to all the vertexes in the original graph with 0 weight edge. Once Bellman Ford is run on the graph and we found any vertex u and edge (u,v) that make d[u] + w[u][v] < d[v], we know there must be a negative cycle leading to u, tracking back from u in the predecessor graph and we'll find the cycle.

DFS is not gonna work in any way, it's obviously not able to exhaust all possible cycles. DFS can be used to find the presence of cycle in graph, but no more.

Answer 2

One clear problem, you're marking the nodes.

 A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

Suppose you take path A->B->D, A B D are grey when you hit D. No cycle is found. You pop out to A; B and D are black. You take the edge, no cycle is found because D is black.

In general, the number of paths is exponential to the size of the graph. You'd have to try every path, there's no way to mark nodes here. If you treated each edge direction in directed graph separately, I believe you'd be able to do this marking the edges, however, this is equivalent to enumerating all paths.