关于代码正确性的第一个问题更适合 http://codereview.stackexchange.com 。

---

贝尔曼福特或 Floyd-Warshall 适用于此问题。性能比较如下：

• 贝尔曼·福特（***）
  
  
  
  • 时间复杂度： O（| V | * | E |）
  
  
  • 空间复杂度： O（| V |）
  
  
  • 有关查找负周期的部分是您想要的
  
  


• 弗洛伊德·沃舍尔（***）
  
  
  
  • 时间复杂度： O（| V | ^ 3）
  
  
  • 空间复杂度： O（| V | ^ 2）
  
  

因为 | E | 受限制 | V | ^ 2 ，贝尔曼·福特是最重要的ar赢家，我会建议您使用它。

---

如果图没有的负周期是在预期的正常情况下，作为算法的第一步，可能需要进行快速检查：图形是否包含负边缘？如果不是，那么它当然不包含任何负循环，并且您有一个 O（| E |）***情况算法来检测是否存在任何负循环。 / p>

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?

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.