bellman福特算法跟蹤

Question

我不知道在哪裏發佈這個問題，我只想知道我是否做了這個跟蹤正確。我給這個圖

，這裏是一個問題：

顯示以下向圖Bellman-Ford算法的痕跡，使用頂點T作爲源。在每一遍中，按（x，t），（y，z），（u，t），（y，x），（u，y），（t，x），（t，y） ），（t，z），（z，x），（z，u）。每次通過後顯示d值。圖表是否有負的加權圓？您如何使用Bellman-Ford算法檢查它？

我得到的答案是u = 12，t = 0，x = 4，y = 12，z = -3，它沒有負加權圓。這個問題值得多點，一個錯誤意味着減去很多，所以我不知道還有誰要檢查這個。謝謝。

Answer 1

在爲了放鬆你指定 -
最初的d值<t = 0, u = inf, x = inf, y = inf, z = inf>

(x, t) <0, inf, inf, inf, inf> 
(y, z) <0, inf, inf, inf, inf> 
(u, t) <0, inf, inf, inf, inf> 
(y, x) <0, inf, inf, inf, inf> 
(u, y) <0, inf, inf, inf, inf> <--Upto this no update because no relaxation started from non-inf 
(t, x) <0, inf, 7, inf, inf> 
(t, y) <0, inf, 7, 12, inf> 
(t, z) <0, inf, 7, 12, -3> 
(z, x) <0, inf, 4, 12, -3> 
(z, u) <0, 12, 4, 12, -3> 

第二次迭代

(x, t) <0, 12, 4, 12, -3> 
(y, z) <0, 12, 4, 12, -3> 
(u, t) <0, 12, 4, 12, -3> 
(y, x) <0, 12, 4, 12, -3> 
(u, y) <0, 12, 4, 12, -3> 
(t, x) <0, 12, 4, 12, -3> 
(t, y) <0, 12, 4, 12, -3> 
(t, z) <0, 12, 4, 12, -3> 
(z, x) <0, 12, 4, 12, -3> 
(z, u) <0, 12, 4, 12, -3> 

因爲它沒有第二次迭代後更改，這是最後的答案，它與你匹配。 也沒有負面的重量循環，因爲整個迭代沒有變化。

注 - 如果邊的順序不同，我們可能預期在第二次迭代中發生變化。