# 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?

## closed as unclear what you're asking by D.W.♦, lPlant, David Richerby, Rick Decker, Guy CoderJul 15 '14 at 19:22

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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