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> 

因为它没有第二次迭代后更改，这是最后的答案，它与你匹配。 也没有负面的重量循环，因为整个迭代没有变化。

注 - 如果边的顺序不同，我们可能预期在第二次迭代中发生变化。