algorithmtracedirected-graphedgesbellman-ford

Bellman-Ford algorithm trace

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

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 have negatively 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 to check this for me. Thank you.

Solution

  • 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>   
(z, u) <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.