Run the Bellman-Ford Algorithm on the directed graph of Figure 24.4, using verte

Question

Run the Bellman-Ford Algorithm on the directed graph of Figure 24.4, using vertex y as the source. In each pass, relax edges in the same order as in the figure, and show the d and values after each pass.

(a) (b) (c) (d) (e) Figure 24.4 The execution of the Bellman-Ford algorithm. The source is vertex s. The d val- ues are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then TIvj u. In this particular example, each pass relaxes the edges in the order (t,x), (t, y), (t, z), (x, t), (y,x), (y, 2), (2,x), z, s). (s, t), (s, y). (a) The situation just before the first pass over the edges. (b) (e) The situation after cach successive pass over the edges. The d and values in part (c) are the final values. The Bellman-Ford algorithm retums TRUE in this example.

Explanation / Answer

y.d = 0, , others inf

edge s-y y.d = 0

edge s-t, t.d = inf

edge t-z = z.d = inf

edge y-x, x.d = 0-3 = -3

edge x-t: t.d = 4-2 = 2

so far we have y.d = 0, t.d = -5, t.x = -3

Now lets use edge y-z,z.d = 9

edge t-z, z.d = -5 -4 = -9

edge z-d, s.d = -9+2 = -7

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.