2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ The graph isn't necessarily connected... So find and process each connected component separately. $\endgroup$ Jan 26, 2021 at 11:48
  • $\begingroup$ 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 $\endgroup$ Jan 26, 2021 at 21:54

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.