Floyd-Warshall算法中不允許使用哪種循環？

比方說

1->2 costs 100 
2->4 costs 600

所以1->2->4成本700

如果有一種是從4到3的邊緣成本覈算-500？而從3不同的邊緣至4成本覈算200

4->3 costs -500 
3->4 costs 200

所以1->2->4->3->4收費400

哪個是小於700

所以被1->2->4->3->4認爲比1->2->4一個較短的路徑???

據我所知，沒有循環是允許的，這是沒有重複邊的路徑的一個例子。

頂點怎麼樣？如果他們重複這是弗洛伊德沃爾索爾的允許週期？

因爲我知道有不同類型的算法，一種允許一種循環，並且不允許其他種類的循環。

有人可以解釋這樣對我？回答這個問題，是1->2->4->3->4考慮比1->2->4更短的路徑？

謝謝大家提前。

編輯：

這裏有一個畫面，顯示你不必訪問同一個邊緣的兩倍。

enter image description here

來源

2014-12-02 ABCD123

維基百科頁面說它不能有任何負面的循環，你的例子。 4-> 3-> 4是一個循環，對不對？ – aardvarkk 2014-12-02 21:32:10

可能是一個更好的網站要問的是[programmers.stackexchange.com]（http://programmers.stackexchange.com） – outlyer 2014-12-02 21:35:44

outlyer，我問過那個網站，並已收到警告。 – ABCD123 2014-12-02 22:07:01

的Floyd-Warshall算法需要與沒有負週期的曲線圖。在你的例子中，4->3->4是一個負循環，因爲循環中權重的總和是-500 + 200 = -300。

來源

2014-12-02 21:35:14 aardvarkk

是的，但是什麼樣的循環？重複邊緣或重複頂點？或兩者？ Floyd Warshall算法的負邊緣是什麼意思？假設沒有周期，但有一個負面的優勢，那好嗎？弗洛伊德·沃肖爾也不允許消極的邊緣嗎？ – ABCD123 2014-12-02 21:39:07

包含循環的圖形是底層圖形本身的屬性，而不是您通過圖形所經過的路徑的屬性。如果一個圖形包含一個負循環（如果可能）採用一條路徑，使得路徑上的權重總和小於零。在上面的例子中，底層圖包含一個循環4-> 3-> 4。例如，如果底層圖不包含有向邊4-> 3，那麼您不必擔心該特定週期。 – aardvarkk 2014-12-02 21:41:04

那麼任何負面的邊緣是不允許的？就好像有一個負面的邊緣，有可能從一個點到另一個點，並且成本小於零。 – ABCD123 2014-12-02 22:46:47

弗洛伊德沃肖爾與約束的算法：graph with no negative cycle，如果你想找到與負週期，你不能用弗洛伊德Warshal圖的最短路徑，這是有原因的考慮與負循環4->3->4你的圖形與成本-300。如果你在這個週期中去一次，你的成本從700減少到400，但爲什麼要在那裏停下來？再去一次，你的費用將是100，並且一次又一次，它將花費你-200,-500，...。你可以永遠做到這一點，算法永遠不會停止。這就是爲什麼在Floyd Warshall算法中有這個約束條件with no negative cycle。

來源

2014-12-02 21:35:53 Lrrr

爲什麼要在那裏停下來？因爲你會重新審視邊緣。在我的例子中，沒有邊被訪問兩次。 – ABCD123 2014-12-02 21:40:56

@ Nebster173這是循環的定義「圖G的循環，是G的邊集的一個子集，它形成一條路徑，使路徑的第一個節點對應於最後一個。」和4-> 3-> 4是一個循環，不管你訪問邊緣有多少次。 – Lrrr 2014-12-02 21:43:19

Floyd-Warshall算法中不允許使用哪種循環？

回答

相關問題