Minimum Spanninjg Tree with vertex weight and edge weight

Question

I am having some troubles solving a problem about Minimum Spanning Tree. So each node in a graph is a city, and is possible to have weight edges connecting two nodes, which is the cost of building a road between two cities. The problem is basically telling the minimum cost of building the roads and have all cities connected some way. I can easily solve this by using Prim or kruskal algorithm to solve this sub-problem of my biggest problem.

The tricky part comes now: Each city (node) can have an airport and each airport has a one time cost (if you decide to build it). You can travel between two cities using an airport if both cities have airports. Now I have to calculate the minimium cost of building roads AND airports in order to have all cities connected, but I am having difficulty representing the connections with the airports with the rest of the network. Can somebody help me here? Maybe I am completely wrong about using MST?

The only solution I came up is: For each city that has an aiport, I will connect that city with another cities that have airports. Also If the cost of building two airports is lower then building a road I take it in consideration. I run kruskal in order to get the cheapest edge, but If kruskal chooses an "airport" edge, I will add it to the spanning tree and then 0 the cost of both airports (if they havent been built in the past). I believe, that by doing this dynamic weight changes while runing kruskal, I am destroyng the idea of getting the minimum cost.

Answer 1

There are two possibilities:

1) The optimal solution does not use airports. In this case you can ignore airports and construct the minimum spanning tree as usual.

2) The optimal solution uses airports. In this case add a dummy node to the graph called "sky". The cost of building a road from any city to "sky" is the cost of building an airport. The cost of the optimal solution using airports is the cost of the minimum spanning tree in this ammended graph.

So try both options and pick the minimum cost.