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.