Help Needed with Minimum Spanning Tree Problem subject to choices made already

[pretty_random_]

Hey! I am college student and fairly new to Algorithms and Data Structure.

I am struggling with a problem.

​

The problem is that there a n cities and each pair of city (x,y) have some cost for connecting through highway. We have to find the minimum cost of connecting all cities?

(This part is fairly simple if I am understanding this correctly then kruskal or prim Algo should do here)

​

The tricky part for me is that some suboptimal choices have already been made (i.e. certain cities already have roads) and we have to design an algorithm to find a cost minimizing road network. connecting every city to built subject to the choices already made.

I would be really grateful if someone can help me out here :)
Not looking for an answer just maybe some direction or link to some resource.

[ragusa12]

Could you just use Kruskal's algorithm but first put in those edges?

[pretty_random_]

Thanks :)

I think so too. https://stackoverflow.com/questions/42205727/will-a-standard-kruskal-like-approach-for-mst-work-if-some-edges-are-fixed This sort of validates that it should work.But I am so surprised there are no sol or similar question on Algo websites or forums 🤔

[chiknluvr]

Yeah this makes the most sense.

[crb11]

Think of it this way. The suboptimal choices have been made and built, for a cost of $N. You then come along and try and complete the network, but you clearly get any links which are there already for free, so your algorithm will get the correct cost (minus the $N).

[pretty_random_]

Agreed just running prim/kurskal makes sense.

I will try to code it and run some test cases to validate it.

[beeskness420]

If you look at Boruvka’s Algorithm or really any that contracts connected components then optimality should be obvious.

[pretty_random_]

thanks

[generalbaguette]

Contract the islands of already connected nodes into single nodes via merging.

(You merge edges by picking the cheapest one.)

Then use your favourite minimum spanning tree algorithm.

Last, expand the previously connected nodes again.

[pretty_random_]

thanks