Take the 2-minute tour ×

I don't know where else to post this question, I just want to know if I did this trace correct. I am given this diagram


and here is the 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 has negative weighted circles ? How do you examine it by using the Bellman-Ford algorithm?

The answer I got was u=12, t=0, x=4, y=12, and z=-3, and it doesn't have a negative weighted circle. This question is worth a lot of points and one mistake means minus a lot, so I don't know who else to have check this for me. Thank you.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Relaxing in the order you specified -
Initially the d values are <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>

Second iteration

(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>   

Since it didn't change after second iteration, this is the final answer, which matched yours. Also there is no negative weight cycle, because of no change in entire iteration.

Note - Had the order of edges, been different, we might have expected change in second iteration.

share|improve this answer
thank you, I was just making sure I wasn't wrong because I got what you got, only after 2 iterations so i thought somewhere i made a mistake. good stuff. thank you –  user1729967 Dec 4 '12 at 7:17

Your Answer


