I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection.

The problem is a minimum cost problem where N ordered sections 1...N all need to be connected. I.e. section N_k needs to be connected to it's adjacent neighbors N_k-1 and N_k+1. The cost function of connecting it to each of the neighbors depends on the value of N_k-1 and also whether or not N_k-1 is already connected to N_k-2 and in that case also the value of N_k-2...

Can anyone direct me to a programming example of a similar problem?

  • $\begingroup$ Please add a reference to the original problem. Why is this important? Reasons 1) Credit should be attributed. 2) The original problem is probably stated clearer, especially when the current question is not clear. 3) A reference will motivate people easily. 4) A reference may save readers who look for related materials lots of time. $\endgroup$ – Apass.Jack Jan 14 at 2:58
  • $\begingroup$ I suspect this problem comes from an ongoing exam or contest because of the way the problem is stated and the lack of update from the asker. I cannot prove beyond reasonable doubt, of course. I will predict: 1) No more reference will be added in the near future. 2) the asker will not be active again. (Of course, I love to see that I will be proven wrong.) $\endgroup$ – Apass.Jack Jan 16 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.