The Bellman Ford algorithm repeats relaxing the entire set of edges |V |1times;
ID: 3829710 • Letter: T
Question
The Bellman Ford algorithm repeats relaxing the entire set of edges |V |1times; in the pseudo-code in pg. 651, i is from 1 to |V | 1. Note that in each iteration edges can be relaxed in an arbitrary order. Consider the following chain graph. The source vertexis s.
What are the values of s.d, a.d, b.d and c.d after exactly one iteration, i.e. just after you relaxall edges for i = 1, when edges are considered in each of the following orders?
(a) (s, a), (a, b), (b, c).
(b) (b, c), (a, b), (s, a).
S) The Bellman Ford algorithm repeats relaxing the en udo-code in pg. 651, i is from 1 to VI-1. Note that n an arbitrary order. Consider the following chain gra ues of s.d. a.d. b. d and c.cd after eaactly one iteration, i 1, when edges are considered in each of the followingExplanation / Answer
a) s.d = 0, a.d = 0+2 = 2, b.d = 2+1 = 3, c.d = 3+3 = 6
b) s.d = 0, c.d = inf, s.b = inf, s.a = 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.