Use Dijkstra to find negative cycles in a graph 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:


  
  Run dijkstra, and mark the distances array as $d$. -- $O(|E| + |V|log|V|)$
  Do relax on each edge -- $O(|E|)$
  For each edge $&lt;u,v&gt; \in E$: -- $O(|E|)$
  
  3.1 if ( $d[v] &lt; d[u] + w(&lt;u,v&gt;)$), report "negative cycle".
  report "No negative cycles"
  


Would this work?
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.