檢測圖中是否存在負循環的最快算法

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|)最佳案例算法用於檢測是否存在任何負循環。