4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – wece May 21 '13 at 14:03
  • $\begingroup$ 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 $\endgroup$ – Loourr May 21 '13 at 14:33
  • $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' May 22 '13 at 22:33
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Loourr May 21 '13 at 23:02
  • $\begingroup$ := 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. $\endgroup$ – David Eisenstat May 21 '13 at 23:09
  • $\begingroup$ I was not questioning what := means but rather what predecessor[v] is, and why its garnered to have a place in the predecessor array? $\endgroup$ – Loourr May 21 '13 at 23:33
  • $\begingroup$ @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. $\endgroup$ – David Eisenstat May 21 '13 at 23:35
  • $\begingroup$ 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". $\endgroup$ – Loourr May 22 '13 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.