Finding minimum possible cost of road network between cities with distance from capital condition

I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E).

Characteristics of the graph:

• Each city is connected to the rest of the graph

• Each city has an index value where the index is equal to minimum number of roads you need to use to get to the capital from this city. Capital has index of 0. The cities connected right to the capital will have index of 1 and so on.

• Some of the roads will be selected to be changed into highways, creating some sort of network.

I would like to find minimum possible cost of said network based on these requirements:

1. It is possible to travel from any city to capital
2. When travelling from any city to capital, the sequence of indexes of visited cities during travel is non-increasing
3. The highway network has to be minimum possible

What I did so far:
I understood this does require MST solution and so I am using Prim's algorithm, but that is solving only part of the problem (req. 1. and possibly 3.) and I need to add something to my MST algorithm to ensure the 2. requirement is fulfilled, and that is my only problem.

I think starting from the capital city might be the first step (and I do so in Prim's), but how to deal with the indexation based on actual road distance from capital city?

Examples:

In the picture 1 below, fig. a) shows incorrect solution using MST algorithm only – one of the possible MST with weight of 35.
Opposed to this, fig. b) shows one of the possible correct solutions with paths with weight of 120.

1 Answer

The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree.

Let's call $$T$$ the solution for the input graph $$G$$. Let's also call $$T_i$$ the solution for the problem $$G_i$$ which is the subgraph of $$G$$ containing vertices with range index lower or equal to $$i$$ (I will use the term "range index" to prevent confusion with the vertex indexing used for Prim's algorithm).

Trivially $$T_0$$ and $$G_0$$ contain only the capital. Now what about $$G_1$$ ?

The cities having a range index of 1 cannot use largest index cities to connect captial. Thus $$T_1$$, which is by the way MST of $$G_1$$, is a subgraph of $$T$$.

$$T_{i+1}$$ is built the same way using $$T_i$$ and $$G_{i+1}$$. The edges of $$T_i$$ are kept and only the new edges to connect the cities having range index $$i+1$$ are added using any MST algorithm.

• Thanks for your input, so I need to add the edges 1 by 1 from the closest range till the farthest range index. Like in the example: starting in vertex 6 I check all direct neighbors (range index 1) and select edge 6-4 (smallest weight), then move onto finding a way between 6 and 5 because it's still in range of 1. Considering the 6-5 is 100 and 6-4-5 is 95, I would add 4-5 to T connecting 6 to 5 via 4. I thought about making an adjacency list with neighbors for each vertex and then traversing it, although I'm not sure how exactly would that work. Oct 14 '20 at 15:03
• In your example you have only one city per range value, so yes you have to treat them in order. But note that it does not match with your description "Each city has an index value where the index is equal to minimum number of roads you need to use to get to the capital from this city. Capital has index of 0. The cities connected right to the capital will have index of 1 and so on.". Anyway, whatever are the index, you have to treat them increasing, all equal indexes at the time. And don't forget, when treating a range level, just consider largest range index cities do not exist. Oct 14 '20 at 15:27