# Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle.
My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the direction I was thinking of but non - fully adressed my concerns. (https://stackoverflow.com/questions/36482398/how-to-print-a-negative-cycle-in-a-graph-g, https://www.geeksforgeeks.org/print-negative-weight-cycle-in-a-directed-graph/).
Here's what I think: So we do the n-th iteration of Bellman -ford and we see some d(p) improve so we know that there is a circle . The thing is that if d(p) was improved that does not mean that v is part of the circle at all cases : "maybe v is reached from s through the circle" .

So all the vectices v that show an improvement of their: d(v) in the n-th iteration are candicates to participate in the circle (let's say we store this in c[]).

• If we take one of these and remove edge (prev[v], v) we can check with a DFS that the graph remains connected in O(V+E). If it does not then definately v is not contained in any circle.
• If it remains connected then we need to perfom another bellman- ford iteration (ignoring (prev[v],v) : if we again see an impovement then we found a vertex contained in the circle if not, discard v as candicate and pick the next vertex to explore from c[].
• When we have found the first vertex u that belongs in the circle we will just iterate backwards because the prev[u] also belongs in the circle and so on.. till we get back to ourself.

First of all , do you think my approach is correct? Second of all, the complexity of what I describe above can have a great cost: we may need many iterations before we find our first vertex belonging to the circle and each may cost us : $$O(VE + V + E)$$. Can we make better?

• Do you want to find all negative weight cycles? Or just all cycles? Jan 14, 2022 at 12:15
• It's "cycle", not "circle" - can you edit your post accordingly?
– D.W.
Jan 14, 2022 at 19:20