In one district of Chennai, there are no roads. Because of heavy rainstorms and floods, getting...

 

Transcribed Image Text:

In one district of Chennai, there are no roads. Because of heavy rainstorms and floods, getting around the villages of that district was particularly difficult because the ground became very muddy. The District Magistrate (DM) has decided that some of the streets must be paved but didn't want to spend more money than necessary. The DM, therefore, specified two conditions: 1. Enough streets must be paved so that it is possible for everyone to travel from their village to anyone else's village only along paved roads, and 2. The paving should cost as little as possible. You have the information about the distance between each village and the length and cost of one stone that is used for making a street. Write the algorithm to connect the best route that connects all the vil- lages, but uses as few paving stones as possible at minimum cost. Give complete analysis and the working example. In one district of Chennai, there are no roads. Because of heavy rainstorms and floods, getting around the villages of that district was particularly difficult because the ground became very muddy. The District Magistrate (DM) has decided that some of the streets must be paved but didn't want to spend more money than necessary. The DM, therefore, specified two conditions: 1. Enough streets must be paved so that it is possible for everyone to travel from their village to anyone else's village only along paved roads, and 2. The paving should cost as little as possible. You have the information about the distance between each village and the length and cost of one stone that is used for making a street. Write the algorithm to connect the best route that connects all the vil- lages, but uses as few paving stones as possible at minimum cost. Give complete analysis and the working example.

Answer rating: 100% (QA)

To find the ... View the full answer