0
$\begingroup$

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?

Improve this question
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.
$\endgroup$
4
  • 1
    $\begingroup$ Please give reference for all the copied text. $\endgroup$
    – Inuyasha Yagami
    May 25 at 20:50
  • $\begingroup$ Hint: Use Dynamic Programming. $\endgroup$
    – Inuyasha Yagami
    May 25 at 20:50
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W. ♦
    May 26 at 6:09
  • $\begingroup$ 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? $\endgroup$
    – Highheath
    2 days ago

0

Reset to default

Your Answer

muhammed gunes is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.