Negative cycle in graph

[Maxim]

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

[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

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

Excuse me.

Can anyone post the pseudocode for Bellman-Ford's Algorithm here?

[Maxim]

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]

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]

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]

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]

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]

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?

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

[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?