Fastest algorithm to detect if there is negative cycle in a graph

Question

I use a matrix d to present a graph. d.(i).(j) means the distance between i and j; v denotes the number of nodes in the graph.

It is possible that there is negative cycle in this graph.

I would like to check if a negative cycle exists. I have written something as follows from a variation of Floyd-Warshall:

let dr = Matrix.copy d in

(* part 1 *)
for i = 0 to v - 1 do
  dr.(i).(i) <- 0
done;

(* part 2 *)
try
  for k = 0 to v - 1 do
    for i = 0 to v - 1 do
      for j = 0 to v - 1 do
          let improvement = dr.(i).(k) + dr.(k).(j) in  
          if improvement < dr.(i).(j) then (
          if (i <> j) then
            dr.(i).(j) <- improvement
          else if improvement < 0 then
            raise BreakLoop )
      done
    done
  done;
  false
with 
  BreakLoop -> true

My questions are

1. Is the code above correct?
2. Is the part 1 useful?

Because I call this function very often, I really want to make it as fast as possible. So my 3) question is if other algorithms (especially Bellman-Ford) can be quicker than that?

Welloff

Answer 1

The first question about the correctness of your code is more appropriate for http://codereview.stackexchange.com.

---

Either of Bellman-Ford or Floyd-Warshall is appropriate for this problem. A comparison of performance follows:

• Bellman-Ford (Wikipedia)
  • Time-complexity: O(|V|*|E|)
  • Space-complexity: O(|V|)
  • The section on "Finding negative cycles" is what you want
• Floyd-Warshall (Wikipedia)
  • Time-complexity: O(|V|^3)
  • Space-complexity: O(|V|^2)

Since |E| is bounded by |V|^2, Bellman-Ford is the clear winner and is what I would advise you use.

---

If graphs without negative cycles is the expected normal case, it might be appropriate to do a quick check as the first step of your algorithm: does the graph contain any negative edges? If not, then it of course does not contain any negative cycles, and you have a O(|E|) best case algorithm for detecting the presence of any negative cycles.

Pique

Thanks for your comment... As my only representation of a graph is a matrix, the step in wiki page of Bellman-Ford for each edge (u, v) with weight w in edges: still needs to be realized by two loops for i = 0 to v - 1 do for j = 0 to v - 1 do .... So for my case, |E| and |V|^2 are quite same, no? – Welloff

@Welloff Oh, I had missed the part about you using a matrix for the graph. In that case, yes, they're the same. :) With that in mind, I'd still say Bellman-Ford has a slight advantage, because of the lesser space-complexity, but I agree you could use either. – Pique

Bellman Ford won't detect a negative cycle if it is not reachable from the source. – Verism

Answer 2

Although the options listed in Timothy Shield's answer are all correct algorithms for finding a negative cycle in a directed weighted graph, they are not the fastest.

My go-to algorithm in this case is always the Shortest Path Faster Algorithm.

Although it has a worst-case time complexity of O(|V|*|E|), which is the same as Bellman-Ford, there are very few graphs for which the SPFA actually reaches that time. In practice, it is much faster, even reaching an (unproven) average time of O(|E|).

I have written an article in my blog explaining the details of using the SPFA to find negative cycles.

If you don't want to read the full article, the pseudocode you need is below.

function SPFA(G):
    for v in V(G):
        len[v] = 0
        dis[v] = 0
        Queue.push(v)
    while !Queue.is_empty():
        u = Queue.pop()
        for (u, v) in E(G):
            if dis[u] + w(u, v) < dis[v]:
                len[v] = len[u] + 1
                if len[v] == n:
                    return "negative cycle detected"
                dis[v] = dis[i] + w(u, v)
                if !Queue.contains(v):
                    Queue.push(v)
    return "no negative cycle detected"

Contexture