Fastest algorithm to detect if there is negative c

问题:

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?

回答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.