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?

  • 1
    $\begingroup$ What do you think? $\endgroup$ – Raphael Jul 14 '14 at 22:44
  • $\begingroup$ 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. $\endgroup$ – TheNotMe Jul 14 '14 at 22:46
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 15 '14 at 0:18
  • 1
    $\begingroup$ In addition, your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – D.W. Jul 15 '14 at 0:19
  • $\begingroup$ I did state out what I could think of... $\endgroup$ – TheNotMe Jul 15 '14 at 0:31

No, it won't work. If your graph has a negative weight edge and Dijkstra computes the shortest paths wrong, then it might be possible to relax an edge (to make the shortest paths correct) even though there is no negative-weight cycle in the graph.

  • $\begingroup$ So, is it even possible to find a negative cycle in $O(|E| + |V|log|V|)$ time? $\endgroup$ – TheNotMe Jul 15 '14 at 0:11
  • $\begingroup$ The fastest algorithm I could find, based on a very brief review, is in [1], which claims an n^2.75 log n running time for integer edge weights in a fixed range -K..K. Even this is more than what you seek. --- Gu, Xiaofeng, et al. "Improved algorithms for detecting negative cost cycles in undirected graphs." Frontiers in Algorithmics. Springer Berlin Heidelberg, 2009. 40-50. $\endgroup$ – Ari Trachtenberg Jul 15 '14 at 0:25
  • $\begingroup$ What do you mean by [1]? $\endgroup$ – TheNotMe Jul 15 '14 at 0:26

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