MinimalSteinerTree 的意思是：
在圖中找出一個生成樹，需要將指定的數(shù)個點連接，邊權(quán)總值最小。
最小生成樹是 MinimalSteinerTree
的一種特殊情況。
此問題是NP完全問題。
在POJ 3123中的標程給出了一個遞歸的算法來解決這個問題。
首先用floyd算法求出兩兩之間的最短路徑。
然后把所有點都兩兩鏈接起來，權(quán)值就是它們的最短路徑。
假設指定必須連接的點有N個。
那么MinimalSteinerTree
樹中的內(nèi)點最多有N-2個。
在紙上畫一下就知道了，內(nèi)點最多的情況就是樹為滿二叉樹的情況。
而由于之前的floyd算法。把整個圖給“縮”了一下。
所以樹最多有N-2+N個點。
枚舉所有可能的點集。對每個點集求最小生成樹。取最小值即可。
另外一種方法是使用動態(tài)規(guī)劃，詳情請見
這里。