7
$\begingroup$

Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a way to do it faster than Floyd-Warshall's $O(|V|^3)$?

$\endgroup$
6
$\begingroup$

If you don't constrain yourself to simple cycles, you can actually use the Bellman-Ford algorithm to find all the relevant vertices.

Start by running a DFS on the graph to find its strongly connected components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ iterations where $V_i$ is the vertices in $G_i$), add $V_i$ to your list of vertices that belong to a negative (not necessarily simple) cycle.

If one of the strongly connected components contain a negative cycle, then because $G_i$ is finite and so are the weights, you can loop through the negative cycle as much as you need, and then add go in a cycle through all the vertices in $G_i$. You only need to loop an amount that will guarantee a total negative cycle.

It is easy to show that there are no cycles between any $G_i,G_j$ and therefore there are no negative cycles other than inside the strongly connected components.

Since you run BF on each subgraph seperately, you keep the time complexity of BF which is $O(|V|\cdot|E|)$.

$\endgroup$
4
$\begingroup$

I was not able to turn up any better algorithm in my research.

In practice, you could improve the running time for many graphs by first decomposing the graph into strongly connected components, then running Floyd-Warshall on each strongly connected component. This does not improve the worst-case complexity (since in the worst case the entire graph could form one large strongly connected component), but it might help on many graphs you're likely to run into in practice.

$\endgroup$
4
  • $\begingroup$ I'm commenting on your answer since O.P is not active anymore. Just to make sure - OP asks about -simple- cycles? Since if we don't constrain the problem to simple cycles, we can find the relevant vertices by breaking the graph to strongly connected components, and then running BF on each component, returning the vertices that are part of a component that had a negative cycle. $\endgroup$ – Mickey Feb 17 '18 at 13:27
  • $\begingroup$ @Mickey, great point! I guess I implicitly assumed simple cycles without realizing it. Oops. Want to write an answer that covers the case of cycles that aren't required to be simple? Or I can edit my answer to incorporate your insight if you prefer -- I just want to give you first chance to write your own answer if you like. $\endgroup$ – D.W. Feb 17 '18 at 18:49
  • $\begingroup$ I have added my answer, feel free to correct/improve it if needed. $\endgroup$ – Mickey Feb 17 '18 at 21:26
  • $\begingroup$ @D.W. will FW algorithm find all vertexes in negative cycle? So, if strongly connected component have at least 2 negative cycles, how FW wil find all of them? $\endgroup$ – Evgeny May 8 '20 at 20:16
1
$\begingroup$

Update

I just realized that my answer below may be incorrect. The intended idea was to perform |V|-1 waves of "relaxation", as in Bellman-Ford (see CLRS). At the end, instead of returning FALSE to denote "negative weight cycle found, so Bellman-Ford failed to find a shortest path tree", we just print the cycle, then continue looking for more cycles to print.

However, it is doubtful (or at least unclear) whether this will actually find all negative weight cycles (or at least simple cycles). For example, if the |V|-1 waves of relaxation only recorded tree edges for extremely negative cycles, but not for moderately negative cycles, then the latter may not be picked up by our print statements, since our print statements only detect cycles that are formed by tree edges.

Original answer

Getting the negative weight cycle is possible with a minor modification to Bellman-Ford.

The implementation of Bellman-Ford in CLRS instantly returns FALSE whenever a negative-weight cycle is found:

BELLMAN-FORD(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i = 1 to |G.V| - 1
    for each edge(u,v) in G.E
      RELAX(u,v,w)
  for each edge(u,v) in G.E
    if v.d > u.d + w(u,v)
      return FALSE
  return TRUE

Instead of returning FALSE, we look at the condition v.d > u.d + w(u,v), which indicates even after |V|-1 passes through all edges, v.d can still be improved. This can only mean that there's a path from v to u through tree edges found during the RELAX loop, for which completing the path with edge (u,v) would cause a negative weight cycle. Hence, to print out the cycle, just follow v and its "parent" pointers all the way up to u. That path plus (u,v) is your negative weight cycle.

$\endgroup$
5
  • $\begingroup$ I don't understand what this has to do with the question. You show how to print the vertices on one negative-weight cycle; but the question asks how to find all vertices on negative-weight cycles. There might be many negative-weight cycles (even exponentially many of them), so this doesn't seem to yield a solution to the question. $\endgroup$ – D.W. Dec 27 '20 at 23:03
  • $\begingroup$ If we replace return FALSE with some print statement, then that print statement is guaranteed to get called for every negative-weight cycle in the graph, since we are checking every edge (u,v) in G.E. Hence, this procedure will in fact print all vertices in negative weight cycles. $\endgroup$ – xdavidliu Dec 27 '20 at 23:15
  • $\begingroup$ OK. I don't see that stated explicitly in the answer at the moment -- can I encourage you to edit your answer to explain explicitly how to find all vertices in negative weight cycles? (Right now the answer talks about "your negative weight cycle" (singular) and "to print out the cycle" (singular), so it might help to discuss multiple cycles explicitly.) It might also help to provide a justification for why this finds all such vertices and show the revised algorithm. $\endgroup$ – D.W. Dec 27 '20 at 23:18
  • $\begingroup$ on second thought, I just realized this answer may be completely bogus (see update I added at beginning). I also considered using ordinary DFS and just looking for "back edges", i.e. edges that go from descendants to ancestors of the DFS tree, since cycles exist if and only if there are back edges. However, the presence of "forward edges" (i.e. non-tree edges going from ancestors to descendants) make it difficult to exhaustively examine all cycles. I would just delete this answer, but I understand that's somewhat discouraged. Let me know if I should just delete it. $\endgroup$ – xdavidliu Dec 28 '20 at 0:00
  • $\begingroup$ That's up to you. I'm not aware of any clear standards for when you should or shouldn't delete your answer, and I'm not familiar with anything discouraging deletion of answers. If you think it has no value or don't want it to appear, as far as I know it is fine to delete it; if you think it still has value or would still like it to be visible to others, as far as I know it is fine to keep it. $\endgroup$ – D.W. Dec 28 '20 at 2:23

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.