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

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.

• Just to clarify, is $a\xrightarrow{1} b \xrightarrow{-2} c \xrightarrow{-1} b \xrightarrow{1} a$ a (negative) cycle? And are you looking for the most efficient algorithm or just a working algorithm (but with a not so good complexity) is enough? – wece May 21 '13 at 14:03
• I would prefer the most efficient, but it dons't have to be. At the same if it's like $O(n^2)$ time on top of bellman ford then I dont want that either. I know that the predisessor array has the information, so really I'm asking how do I extract it. And more like a->b = 1, b->d = -3, d->a = 1, but really just any negative weight cycle – Loourr May 21 '13 at 14:33
• We already have a question on this topic: Getting negative cycle using Bellman Ford. Does that thread answer your question? If not, please edit your question to state what you still need answered. – Gilles May 22 '13 at 22:33