Negative Weight Cycle Algorithm

Question

I was thinking of an algorithm for finding a negative weight cycle in a directed graph. The problem is that we have a graph G (V, E), we need to find an effective algorithm for finding a cycle with a negative weight. I understand the algorithm in this pdf

In short, the algorithm applies the Bellman Ford algorithm by iterating | V | -1 times, doing relaxation. After that, he checks if there is an edge that can even be softened more, then there is a negative weight cycle, and we can trace it back with parent pointers, and everything goes well, we find a negative weight cycle.

However, I was thinking of another algorithm for using deep search (DFS) in the graph, tracking the sum of distances so far covered, I mark all nodes white at the beginning and turn them gray when I search for the path and mark them black when they are finished, so I know that I find a loop if and only if I find a visited node and it is gray (in my path), and not black, which was already completed by Depth-First search, and therefore for my algorithm, if I get to gray node that has already been visited, I check that it will update (new distance), and if it is less than before, I know that I have a negative weight cycle and you can trace it.

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

thanks

Answer 1

One obvious problem, you mark nodes.

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

Suppose you choose the path A-> B-> D, ABD gray when you press D. No loop found. You exit onto A; B and D are black. You take the edge, no loop was found because D is black.

In general, the number of paths exponentially depends on the size of the graph. You have to try every path, there is no way to mark nodes. If you relate to each direction of the edge in an oriented graph separately, I believe that you can do this by marking the edges, however this is equivalent to listing all the paths.

Answer 2

Bellman Ford does not always work, the problem lies in its algorithm with a single source of the shortest path , if the negative loop is not available from the source you choose, it fails. However, a small change to Bellman Ford could help, instead of selecting the source vertex and initializing its distance to 0, we can initialize the entire distance to 0, and then start Bellman Ford. This is equivalent to adding an additional vertex s', which points to all the vertices of the original graph with 0 weighted edge. As soon as Bellman Ford starts on the chart, and we find any vertex u and edge (u, v) that make d [u] + w [u] [v] d [v], we know that there must be a negative cycle, leading to u, tracking from u in the predecessor graph, and we will find a loop.

DFS will not work in any way; it will obviously not be able to exhaust all possible cycles. DFS can be used to find the presence of a loop in a graph, but no more.

Answer 3

I believe there is a way to solve this in linear time. When searching a graph with a deep search (DFS has an O (V + E) runtime), you can track the distance from the source to the current node (simply by increasing the parent distance with the weight of the edge connecting the node's child to the parent). Then, whenever you encounter a loop (loops are detected by finding the trailing edge on an undirected graph or either the trailing edge or the leading edge in a oriented graph), you can subtract the distance between the source node and the root of the node cycle from the distance between the source source and the final node in the loop (the root of the node is the node where the loop started). If the result is negative, the loop must be negative!