Negative Weight Cycle Algorithm

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.

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.