Question

Each road is associated with a value indicating the level of danger in maintaining that road during winter months. There are many subsets of roads such that the roads in such subsets keep the towns connected directly or indirectly. Each subset is assigned a cost of maintenance, which is directly proportional to the highest danger level of the road present in that subset. The engineer wants to select the smallest subset that keeps the towns connected directly or indirectly and that also has the lowest cost of maintenance. Develop an algorithm to find such a subset. Justify the correctness of your algorithm and derive its runtime.

Answer 1

Each road is associated with a value indicating the level of danger in maintaining that road during winter months. There are many subsets of roads such that the roads in such subsets keep the towns connected directly or indirectly.