There was a village that had no roads. Getting around the village was particular

Question

There was a village that had no roads. Getting around the village was particularly difficult after rainstorms because the ground became very muddy, cars got stuck in the mud and people got their shoes dirty. The mayor of the village decided that some of the streets must be paved, but didn't want to spend more money than necessary. The mayor therefore specified two conditions: Enough streets must be paved so that it is possible for everyone to travel from their house to anyone else's house only along paved roads, and The paving should cost as little as possible. Below is the layout of the city. The number of paving stones between each house Represents the cost of paving that route. Write an algorithm to find the best route that connects all the houses, but uses as few paving stones as possible.

Explanation / Answer

This can be solved by using Johnson's algorithm.Let the houses be numbered as the vertices(nodes) from 1 to 10. Let it be stored in the set V={V1, V2,...V10}

The number of paving stones represent the edge of connecting two vertices, e.g w(1,2)= 5

all theses edges are stored in set E.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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