# Detecting cycles with weight zero in a directed graph

I am given a directed graph $$G=(V, E)$$ with a weight function $$w: E\to\mathbb{R}$$, that doesn't contain negative cycles.

I need to find an algorithm that returns true if and only if there is a cycle with weight zero in the graph.

The time complexity needs to be $$O(|V||E|)$$, so I thought about using Bellman-Ford algorithm, but I have two problems with that:

First, the graph doesn't necessarily connected, so I can't pick an arbitrary source vertex for the algorithm.

Second, I can't figure out how the algorithm can help me, and what I can do with its output.

I know that a similar question have been asked, but the answer just suggests to run Bellman-Ford algorithm, but as I mentioned, I can't choose a source vertex. In addition, I don't understand why the suggested answer will work at all.

• The graph isn't necessarily connected... So find and process each connected component separately. Commented Jan 26, 2021 at 11:48
• I have added the proof of the statement that was left as an exercise by D,W. You will be able to understand it now. Check the proof: cs.stackexchange.com/a/134819/107966 Commented Jan 26, 2021 at 21:54

Add a new vertex $$s_0$$. Add edges of weight 0 from $$s_0$$ to each other vertex. Now you have a graph with a source vertex $$s_0$$. Run the previously mentioned algorithm on this new graph, using $$s_0$$ as the source vertex.