检测图中是否存在负循环的最快算法

Question

我使用矩阵d来呈现图。 d.(i).(j)表示i与j之间的距离; v表示图中节点的数量。

这个图表中可能有负循环。

我想检查是否存在负循环。我写的东西从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 

我的问题是

1. 上面是正确的代码？
2. 是part 1有用吗？

因为我经常调用这个函数，我真的想尽可能快地调用它。所以我的问题是如果其他算法（尤其是Bellman-Ford）可以比那更快？

Answer 1

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

---

的任Bellman-Ford或Floyd-Warshall适合于这个问题。业绩比较如下：

• Bellman-Ford（维基百科）
  • 时间复杂度：O(|V|*|E|)
  • 空间复杂度：O(|V|)
  • The section on "Finding negative cycles"是你想要
• Floyd-Warshall什么（维基百科）
  • 时间复杂度：O(|V|^3)
  • 空间复杂度：O(|V|^2)

由于|E|由|V|^2界，Bellman-Ford是明显的赢家，是什么，我会建议你使用。

---

如果图表没有负周期是预期的正常情况下，它可能是适当做一个快速检查作为你的算法的第一步：不图包含任何负面的边缘？如果不是，那么它当然不包含任何负循环，并且您有一个O(|E|)最佳案例算法用于检测是否存在任何负循环。