A TV cable is to be installed in a living mom (LR) of a house. The only requirem

Question

A TV cable is to be installed in a living mom (LR) of a house. The only requirement is that every room in the house he connected by some route to the living room (call them A. B. C. D. E). The charge for the special TV cable is $100 per meter, where the distance (in meter) between every pair of rooms is as follows: Use the algorithm of the minimum spanning tree problem to determine which pairs of moms should be directly connected by special cable lines in order to connect every room (directly or indirectly) to the living room at a minimum total cost.

Explanation / Answer

Shortest Path to all rooms

Total distance for the shortest path {LR,B,A,E,C,D} = 7+10+5+8+17.5 = 43.5 m

Total cost = 100*47.5 = $4750

Visited LR A B C D E {LR} 0 19 7 11.5 27 16 {LR,B} 0 19 7 11.5 27 16 {LR,B,A} 0 17 7 11.5 27 16 {LR,B,A,E} 0 17 7 11.5 27 16 {LR,B,A,E,C} 0 17 7 11.5 27 16 {LR,B,A,E,C,D} 0 17 7 11.5 27 16

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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