2 minimum-cost pipeline is to be laid between towns A and E. The pipeline is req

Question

2 minimum-cost pipeline is to be laid between towns A and E. The pipeline is required to pass through one node out of B, B2, and Ba, one out of C1, C2, and Cs, and one out of D1, D2, and Ds (see Figure Q2 below). B1 D2 D3 Figure Q2 Find the solution using dynamic programming. The relative costs associated with the various segments of the pipeline are given below: 20 marks] For the segment starting at A A-B1 A-B2 A-B3 For the segment ending at E 10 15 D1-E D2-E 12Ds-E12 For the segments B, to C and C to D From node i To node 2 12 19 13 14 3 15

Explanation / Answer

The following information can be extracted from the problem statement to make it simpler:

Our base cases would be:
T1 = A-B1 = 10
T2 = A-B2 = 15
T3 = A-B3 = 12.

Using the base case relation and the recursive relation, we get the path as AB1C1D1E with a minimum cost path of 35.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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