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
Commented May 21, 2013 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 Commented May 21, 2013 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. Commented May 22, 2013 at 22:33

• Some points of confusion. by "every node u" you mean, for every node u in predecessor? What do you mean by "while v is white and has a predecessor"? and what does it mean to set v := predecessor[v]? Thanks for the answering - @David Eisenstat Commented May 21, 2013 at 23:02
• I was not questioning what := means but rather what predecessor[v] is, and why its garnered to have a place in the predecessor array? Commented May 21, 2013 at 23:33
• So in the step for i from 1 to size(vertices)-1: do I want to be doing for i from 1 to size(vertices)? and I'm still not sure what you mean by v "has a predecessor". Commented May 22, 2013 at 3:02