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?

Answer 1

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"

Answer 2

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.