# Designing Algorithm for MST problem for a optical fiber network bounded by costs

So I need to design an algorithm for the following problem:

Suppose we need to build an optical fibre network for 20 cities. We are given a distance matrix of the cities which tells us which cities are connected so that we can make a connection between them and a cost matrix which tells us how much each connection costs (not every city must be connected). The company which builds this network wants a network such that the used cable is minimal(minimal cable length) and that the costs are below a given constant.

This is the algorithm I got so far:

1. Use Prims algorithm to obtain a MST:
• if the costs of this MST is below or equal the given constant we are done so the program stops
• if it is greater than go to the next step.

We have a MST with costs greater than the given constant. We denote the MST as T

1. Calculate the difference of costs of T with the given constant ie. T-c
• if T-c >0, do the following: Take the most expensive edge T and remove it. Now we have T-{e} which are 2 subtrees. Search for a cheaper edge which minimal length such that it connects the 2 subtrees(we do not want a cycle) and connect it and you have a tree T' with less costs and less length.

• if there is no cheaper edge with less length after we remove the most expensive edge then try it for the second most expensive and so on.

If T-c ≤0 then we obtain a spanning tree which is below c and is not minimal necessarily.

Now this algorithm will stop if T-c ≤ 0, which means that we stop when the costs are below c, but that does not mean that this is the MST we are looking for. For example the could be a tree with less length wich cost less than the one we obtained by this algorithm. How can I fix this and are there any tips to improve my algorithm?

New contributor
muhammed gunes is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Please give reference for all the copied text. May 25 at 20:50
• Hint: Use Dynamic Programming. May 25 at 20:50
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
May 26 at 6:09
• I don't exactly understand what you mean. Prim's algorithm already give you a minimum spanning tree, i.e. a spanning tree with the lowest possible cost. If the cost of T is above c, then there is no MST with a cost at most c. Are there any constraints you haven't explained properly, that makes it so not all MST's are valid? 2 days ago