Bellman-Ford算法檢測到什麼？負重或負週期？

Question

如果我們給出一個圖，現在我們從源計算最短路徑。現在，如果一個邊具有負權重，但是在到達目的地時返回邊緣的邊緣有邊緣，我的意思是如果沒有循環，那麼我們沒有負循環。但維基百科中的here給定的算法從源再次運行，因此它檢測到負邊權重但不是負週期。我的問題是，如何確定一個負循環？

Answer 1

負重量週期是一個週期，其權重總和爲負數。 Bellman-Ford算法以V-1步驟向圖中的所有節點傳播正確的距離估計，除非有負的權重循環。如果存在負重量循環，則可以無限期地放鬆其節點。因此，如在維基百科算法中看到的，在V-1步驟之後放鬆邊緣的能力是測試負重量週期的存在。因此，Bellman-Ford算法測試負重量週期。