CODEWITHSUNDEEP
algorithmdata-structures
Abhi
Abhi

Reputation: 61

Algorithm: Minimum length of road to be built to connect all the cities of the state to either of the two airports of the state

Assume a state has 10 cities A,B,C,D,E,F,G,H,I,J. Now let's say D and G both have an airport. Given the distance of each city from one another, what is the minimum length of road that should be built so that all the cities are connected to an airport? There can be a direct route or indirect route (i.e. via some other city) from each cities to an airport; our objective is to construct minimum length of road.

Upvotes: 3

Views: 1022

Answers (1)

akappa
akappa

Reputation: 10490

Your problem reduces to the minimum spanning tree problem by simply chaining together the vertexes associated to airports with edges of zero weight. As such, you can solve it by using e.g. the classical Prim algorithm:

  1. Initialize the solution with all the vertexes containing an airport
  2. Among all the remaining edges, select the cheapest one that augments the spanning tree
  3. Iterate until every vertex is covered.

Upvotes: 6

Related Questions