title: Negative Weight Cycle Algorithm
body: <p>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. <a href="http://www.cs.arizona.edu/classes/cs445/spring05/ShortestPath2.prn.pdf" rel="noreferrer">I understand the algorithm in this PDF document</a> </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Is my algorithm wrong? If so, can you find a counterexample ? If not can you help me prove it?</p>
  
  <p>Thank You</p>