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.
