Bellman算法跟踪

Question

我不知道还能在哪里发布这个问题，我只想知道我是否正确地做了这个跟踪。我得到了这张图表

​

​

以下是一个问题：

在以下有向图上显示Bellman算法的跟踪，使用顶点t作为源。在每次传递中，按(x，t)，(y，z)，(u，t)，(y，x)，(u，y)，(t，x)，(t，y)，(t，z)，(z，u)的顺序松弛边。每次传递后显示d值。这个图有负加权圆吗？你如何用Bellman算法来检验它呢？

我得到的答案是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>

由于它在第二次迭代后没有改变，这是最后的答案，它与您的答案相匹配。此外，没有负权循环，因为在整个迭代中没有变化。

注:如果边的顺序不同，我们可能会在第二次迭代中预料到变化。