Finding the path of a negative weight cycle using Bellman-Ford

Question Detail: 

I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, which path do I actually trace to get to the original vertex having traveled a negative amount.

So to be clear say I have a graph with vertexes, a, b, c, and d and there is a negative cycle between a, b, and d, then when I check for negative weight cycles

// Step 1: initialize graph    for each vertex v in vertices:        if v is source then distance[v] := 0        else distance[v] := infinity        predecessor[v] := null     // Step 2: relax edges repeatedly    for i from 1 to size(vertices)-1:        for each edge (u, v) with weight w in edges:            if distance[u] + w < distance[v]:                distance[v] := distance[u] + w                predecessor[v] := u     // Step 3: check for negative-weight cycles    for each edge (u, v) with weight w in edges:        if distance[u] + w < distance[v]:            "Graph contains a negative-weight cycle" 

Instead of it just telling me that a negative cycle is there, I would like it to tell me, go from a -> b -> d -> a. After the relaxing step what do I have to change in my check for negative weight cycles to get it to output this information?

• Here is the best information I've been able to find, but I'm still having trouble making sense of it.

• Also this which suggests that I need to run breadth first search on the predecessor array to find the information, but I'm not exactly sure where to start (what do I queue first?)

• Here is a stack overflow question which shows how to find one of the nodes in the path.

Asked By : Loourr

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12129

Answered By : David Eisenstat

Per Kleinberg–Tardos, you want to run Bellman–Ford for n iterations and find a cycle in the predecessor array.

To find a cycle in the predecessor array, start by coloring every node white. For each node u in an arbitrary order, set v := u, and, while v is white and has a predecessor, recolor v gray and set v := predecessor[v]. Upon exiting the loop, if v is gray, we found a cycle; loop through again to read it off. Otherwise, none of the gray nodes are involved in a cycle; loop through again to recolor them black.