# Use Dijkstra to find negative cycles in a graph [closed]

I will state the problem:

Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph.

So, I saw the runtime, and I immediately said we need to use Dijsktra's implementation with a fibonacci heap. I suggested the following:

1. Run dijkstra, and mark the distances array as $d$. -- $O(|E| + |V|log|V|)$

2. Do relax on each edge -- $O(|E|)$

3. For each edge $<u,v> \in E$: -- $O(|E|)$

3.1 if ( $d[v] < d[u] + w(<u,v>)$), report "negative cycle".

4. report "No negative cycles"

Would this work?

• What do you think? – Raphael Jul 14 '14 at 22:44
• I'm not sure. When I think about it, if there is a negative cycle then we will surely detect it. But all the computation prior to that would be wrong, since dijkstra can't even handle negative edges... I need your help. – TheNotMe Jul 14 '14 at 22:46
• What have you tried? Have you tried running it on some example graphs to see if you can find a counterexample? Have you tried proving your algorithm correct? This site is not here to solve your exercises for you, nor to check whether your answers are correct. We expect you to make a serious effort before asking and to show us in the question what you have tried. You can help us help you by making a more significant effort, and showing us in the question what you have tried. Asking here should be a last resort only after you've tried everything else you can think of. – D.W. Jul 15 '14 at 0:18
• So, is it even possible to find a negative cycle in $O(|E| + |V|log|V|)$ time? – TheNotMe Jul 15 '14 at 0:11