Page 1 of 1
Negative cycle in graph
Posted: Fri May 30, 2003 11:52 am
by Maxim
Given directed weighted graph determine a negative cycle C, (c1,c2,
Posted: Fri May 30, 2003 12:29 pm
by Dominik Michniewski
I think that it's possible to do that using Bellman-Ford (if you remember vertices which are previos to actual), but I could be wrong, because I didn't try it ... Time complexity should be the same as Bellman-Ford algorithm ....
Best regards
DM
Posted: Sat May 31, 2003 1:16 pm
by junjieliang
I haven't done this before, but I think you can store the parent of each node, then once you find a cycle, start tracing. Stop when you encounter the same node twice. You should be able to find a cycle this way.
Time complexity: O(VE + V) I think, O(VE) for Bellman-Ford, O(V) at most for tracing.
Posted: Sun Jun 01, 2003 9:27 am
by Observer
Excuse me.
Can anyone post the pseudocode for Bellman-Ford's Algorithm here?
Posted: Sun Jun 01, 2003 1:09 pm
by Maxim
Observer wrote:Excuse me.
Can anyone post the pseudocode for Bellman-Ford's Algorithm here?
Code: Select all
d[i] <- infinity for each i except for source (i.e. starting node), so d[source] <- 0
for i <- 1 to |V[G]| - 1
do for each edge (u, v) in E[G]
if d[v] > d[u] + w(u, v)
d[v] <- d[u] + w(u, v)
If you want to know if there is a negative-weight cycle, insert these following lines after those above:
Code: Select all
for each edge (u, v) in E[G]
do if d[v] > d[u] + w(u, v) then output "negative-weight cycle detected"
That means that if you can still do relaxation after |V[G]| - 1 steps, there must be negative-weight cycle.
This pseudo code was taken from Introduction to Algorithms - Cormen, Leiserson, Rivest.
Maxim
Posted: Sun Jun 01, 2003 3:43 pm
by Kuba12
I think you can also use Dijkstra to solve this problem. If you find a shorter path to a node that has already been processed, you have a negative cycle. Time compexity should be much better.
need something better
Posted: Mon Jun 02, 2003 1:16 pm
by Maxim
I've found a negative-weight cycle (cycle itself) with Floyd-Warshall in O(n^4). Please, does anyone know how to do it faster? I need to do it in dynamic graph and remove them after detected, so it would take really long to complete it. I
Posted: Mon Jun 02, 2003 2:34 pm
by ChristopherH
See my comment near the end of the thread on 10449:
http://acm.uva.es/board/viewtopic.php?t=2306
for a simple modification to Bellman-Ford which will identify exactly the nodes on negative-weight cycles in total time O(VE).
Dijsktra doesn't work, even for finding cycles reachable from a given source. You can end up revisiting a vertex with a lower total cost without a negative-weight cycle.
e.g. the digraph
Dijkstra from A will first visit B with total cost 10, then find the path ACB with cost 5. Yet there is no negative cycle.
(If you start patching Dijkstra with relaxation etc, you end up with something essentially Bellman-Ford).
Posted: Mon Jun 02, 2003 7:33 pm
by Kuba12
Somehow I got AC for problem 558 (Wormholes) using Dijkstra algorithm. Do you think that inputs used to judge it are not difficult enough?[/cpp]
Posted: Fri Jun 06, 2003 8:59 pm
by makbet
My friend has also solved this problem using Dijkstra, which made me totally confused.
Maybe there's something in the problem description that we've missed?
Posted: Sat Jun 07, 2003 8:04 am
by Whinii F.
I also solved the problem Wormhole with Dijkstra. It's quite a few months ago (when I didn't know about Bellman-Ford) so I don't remember all the details but I think I did prove that the problem could be solved with Dijkstra.. I'm not much sure about it, anyway..
Posted: Sat Jun 07, 2003 8:51 am
by makbet
The algorithm which uses dijkstra works alright when you have
bi-directional edges. But in this problem the edges are directed. Maybe I'm still missing something?