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:
- It is possible to travel from any city to capital
- When travelling from any city to capital, the sequence of indexes of visited cities during travel is non-increasing
- 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?
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.