Search code examples
algorithmgraph-algorithmbellman-ford

Negative Weight Cycle Algorithm

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

Solution

  • 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.