# 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

## 1 Answer

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.

• 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 – Loourr May 21 '13 at 23:02
• := is the assignment operator. The while condition is meaningful because v changes. I meant every node u, though it would suffice to consider only the ones with non-null predecessors. – David Eisenstat May 21 '13 at 23:09
• I was not questioning what := means but rather what predecessor[v] is, and why its garnered to have a place in the predecessor array? – Loourr May 21 '13 at 23:33
• @Loourr predecessor[v] is the tail of the arc most recently relaxed among those having head v, just like in your pseudocode for B–F. – David Eisenstat May 21 '13 at 23:35
• 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". – Loourr May 22 '13 at 3:02