0
$\begingroup$

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" . enter image description here

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?

$\endgroup$
5
  • 1
    $\begingroup$ Do you want to find all negative weight cycles? Or just all cycles? $\endgroup$
    – nir shahar
    Jan 14, 2022 at 12:15
  • $\begingroup$ It's "cycle", not "circle" - can you edit your post accordingly? $\endgroup$
    – D.W.
    Jan 14, 2022 at 19:20
  • $\begingroup$ Is your question answered by cs.stackexchange.com/q/109485/755, cs.stackexchange.com/q/12129/755, cs.stackexchange.com/q/6919/755, cs.stackexchange.com/q/27712/755? If not, please edit your question to make clear what you are asking. In the future, before asking please spend some time searching this site to check whether your question might have been answered already, and to help you make clear what you are asking. $\endgroup$
    – D.W.
    Jan 14, 2022 at 19:24
  • $\begingroup$ @D.W. it's not : they do not provide any detail $\endgroup$ Jan 14, 2022 at 19:48
  • 1
    $\begingroup$ OK, great! Then I encourage you to study the material there, pick one specific detail that you don't understand, and ask a new question about that one detail, to provide some summary and background, and make sure it is clear how this question differs from those others. Or, you could edit this post. Please ask only one question per post. The question can be considered for re-opening if it is clear what you are asking and it is clearly differentiated from prior questions. $\endgroup$
    – D.W.
    Jan 14, 2022 at 20:16

0