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