Problem Detail: 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 $<u,v> in E$: — $O(|E|)$ 3.1 if ( $d[v] < d[u] + w(<u,v>)$), report “negative cycle”.
- report “No negative cycles”
Would this work?
Asked By : TheNotMe
Answered By : Ari Trachtenberg
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28414 Ask a Question Download Related Notes/Documents
