贝尔-福德算法追踪

Question

贝尔-福德算法追踪

algorithmtracedirected-graphedgesbellman-ford

3

我不知道在哪里发布这个问题，我只想知道我是否正确地追踪了它。我被给予这个图表，并且以下是问题：

用顶点t作为源，在以下有向图上显示Bellman-Ford算法的跟踪，按照(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，它没有负权重圆。这个问题很值钱，一个错误意味着扣除很多分数，所以我不知道还有谁可以帮我检查这个问题。谢谢。

- user1729967

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vinayak Garg · Accepted Answer

按照您指定的顺序进行松弛 -
最初的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>

由于第二次迭代后它没有改变，这就是最终答案，与您的匹配。此外，由于整个迭代过程中没有任何变化，因此不存在负权重循环。

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