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

Question

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.

Answer 1

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.