Negative cycle in graph

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Negative cycle in graph

Post by Maxim »

Given directed weighted graph determine a negative cycle C, (c1,c2,

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post 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
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)

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post 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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Excuse me.

Can anyone post the pseudocode for Bellman-Ford's Algorithm here?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post 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

Kuba12
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

Post 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.

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

need something better

Post 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

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post 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

Code: Select all

A B 10
A C 20
C B -15
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).

Kuba12
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

Post 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]

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post 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? :wink:

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post 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.. :D
JongMan @ Yonsei

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post 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? :wink:

Post Reply

Return to “Algorithms”