4
$\begingroup$

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|).

I was thinking about using Bellman-Ford to solve the question doing this: Do |V| iterations of Bellman-Ford, If there were no changes on the last iteration, there is no cycle of negative weight in the graph. Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found. This cycle will be the desired cycle of negative weight.

The problem is, that no start vertex is given, and Bellman-Ford notes wether there is reachable negative cycle via the start vertex or not. Assume that if we start from vertex a there won't be negative cycle and if the start vertex was b there will be one. So if I choose a as a start vertex I'll miss the negative graph.

How can I solve that? I thought about trying all the vertexes as start vertex but it won't be O(|E|*|V|).

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you taken a look at this question, for instance? $\endgroup$
    – dkaeae
    Commented May 17, 2019 at 15:11
  • $\begingroup$ The problem in the given algorithm is that it only finds a negative cycle that is reachable from the starting vertex. Am I wrong? $\endgroup$
    – Sama Assi
    Commented May 17, 2019 at 15:15
  • $\begingroup$ Well, if your graph is connected (in the sense that there is one vertex from which all other vertices are reachable) anyway, then it doesn't seem to matter. And, if the graph is not connected, you only need break it down to its components. $\endgroup$
    – dkaeae
    Commented May 17, 2019 at 15:34
  • $\begingroup$ It's not component. How would it help me breaking the graph to its components? $\endgroup$
    – Sama Assi
    Commented May 17, 2019 at 15:36
  • $\begingroup$ If you have $k$ disjoint components, then you run the algorithm in the linked question on each component. You can even do so in parallel. $\endgroup$
    – dkaeae
    Commented May 17, 2019 at 15:43

1 Answer 1

Reset to default
2
$\begingroup$

Choosing a arbitrary vertex as source may not reach the negative cycle in the graph.

Assuming the graph is directed. The cycle may not be visited if there are vertices that the source node cannot reach, such as: (assuming $V_0$ is the source)

  • Graph containing different components or

  • There are vertices behind the source vertex.

So, the solution is to:

  1. Set Dist[v]=0 for all v that has 0 in-degree (or alternatively, add an additional vertex as source, which connects to all other vertices with 0-weighted edges. (similar to Johnson's algorithm))
  2. Run Bellman-Ford for V-1 iterations
  3. Perform an additional iteration for marking negative paths (by ancestor backtracking)
  4. Maintaining the minimum cycle while perform a BFS starting from the 0-in-degree vertices.
Improve this answer
$\endgroup$
2
  • $\begingroup$ @ J3soon Could you explain step 4 in more detail? $\endgroup$
    – Marian13
    Commented Jul 13, 2020 at 11:05
  • $\begingroup$ Just fullfil @J3soon answer (I can not comment) step 3: while Bellman-Ford you remember ancestor which leads to decreasing of value of node. step 4: run BFS (for shortest cycle) or DFS on nodes ancestors from step3. When you reach some node second time - you found cycle. $\endgroup$
    – Jaroslav Holeček
    Commented May 2, 2021 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.