Run the Bellman-Ford algorithm on the graph G below, where s is the source verte
ID: 3718639 • Letter: R
Question
Run the Bellman-Ford algorithm on the graph G below, where s is the source vertex. Indicate the order of edges that you use for relaxations. Write the v.d and v.tr values of each vertex after each iteration of relaxations. Darken the shortest-paths tree. Does the algorithm return TRUE or FALSE? If returns FALSE, for which edges (u, v) is the inequality v.d > u.d + w(u,v) satisfied?. Use the algorithm learned in class. Use your Z number21 22 23 24 25 26 27 28 to find the weights of the edges in the graph. If any digit in your Z number is equal to zero, then substitute it by 5. -14 For example if your Z number is 12345678, then the graph becomes: w *OExplanation / Answer
I'm using the Z number given in the question i.e 12345678 the graph and the weights will be as shown in the question.
The source vertex is s , therefore s.d=0 and s.pi=NIL.
The order of relaxation that I will follow is (s,a) , (b,a) , (c,s) , (c,b) , (a,c).
As there are 4 vertices there will be 3 iterations and even if value of d decreases in 4th iteration then the algorithm will return false.
IST ITERATION:
relax(s,a)
a.d=6
a.pi=s
relax(b,a)
no change
relax(c,s)
no change
relax(c,b)
no change
relax(a,c)
no change
2ND ITERATION:
relax(s,a)
no change
relax(b,a)
no change
relax(c,s)
no change
relax(c,b)
no change
relax(a,c)
c.d=-8
c.pi=a
3RD ITERATION:
relax(s,a)
no change
relax(b,a)
no change
relax(c,s)
s.d=-3
s.pi=c
relax(c,b)
b.d=-4
b.pi=c
relax(a,c)
no change
4TH ITERATION:
relax(s,a)
a.d=3
a.pi=s
relax(b,a)
a.d=-1
a.pi=b
relax(c,s)
no change
relax(c,b)
no change
relax(a,c)
no change
As for edges (s,a) and (b,a) it is still relaxing in 4th iteration so the algorithm will return false.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.