この質問を他にどこに投稿すればよいかわかりません。このトレースを正しく行ったかどうかを知りたいだけです。私はこの図を与えられます
そしてここに質問があります：
頂点tをソースとして使用して、ベルマンフォードアルゴリズムのトレースを次の有向グラフに表示します。各パスで、（x、t）、（y、z）、（u、t）、（y、x）、（u、y）、（t、x）、（t、yの順序でエッジを緩和します）、（t、z）、（z、x）、（z、u）。各パスの後にd値を表示します。グラフには負の重みの円がありますか？ベルマンフォードアルゴリズムを使用して、それをどのように調べますか？
私が得た答えは、u = 12、t = 0、x = 4、y = 12、およびz = -3であり、負の重み付きの円はありません。この質問は多くのポイントの価値があり、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>
2回目の反復
(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>
2回目の反復後も変化しなかったため、これが最終的な答えであり、あなたの答えと一致しました。また、反復全体に変化がないため、負の重みサイクルはありません。
注-エッジの順序が異なっていた場合、2回目の反復で変更が予想された可能性があります。