algorithm - Bellman-Ford 算法轨迹

Question

我不知道还有什么地方可以发布这个问题，我只想知道我是否正确地进行了跟踪。我得到了这张图

问题是:

Show the trace of the Bellman-Ford algorithm on the following directed graph, using vertex t as the source. In each pass, relax edges in the order of(x, t),(y, z),(u, t),(y, x),(u, y),(t, x),(t, y), (t, z),(z, x),(z, u). Show the d values after each pass. Does the graph have negatively weighted circles? How do you examine it by using the Bellman-Ford algorithm?

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

由于它在第二次迭代后没有改变，所以这是最终答案，与您的匹配。也没有负权重循环，因为整个迭代没有变化。

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