Negative cycle in graph
Moderator: Board moderators
Negative cycle in graph
Given directed weighted graph determine a negative cycle C, (c1,c2,

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I think that it's possible to do that using BellmanFord (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 BellmanFord algorithm ....
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Excuse me.
Can anyone post the pseudocode for BellmanFord's Algorithm here?
Can anyone post the pseudocode for BellmanFord's Algorithm here?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer wrote:Excuse me.
Can anyone post the pseudocode for BellmanFord'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)
Code: Select all
for each edge (u, v) in E[G]
do if d[v] > d[u] + w(u, v) then output "negativeweight cycle detected"
This pseudo code was taken from Introduction to Algorithms  Cormen, Leiserson, Rivest.
Maxim
need something better
I've found a negativeweight cycle (cycle itself) with FloydWarshall 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

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
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 BellmanFord which will identify exactly the nodes on negativeweight 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 negativeweight 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 BellmanFord).
http://acm.uva.es/board/viewtopic.php?t=2306
for a simple modification to BellmanFord which will identify exactly the nodes on negativeweight 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 negativeweight cycle.
e.g. the digraph
Code: Select all
A B 10
A C 20
C B 15
(If you start patching Dijkstra with relaxation etc, you end up with something essentially BellmanFord).