你誤會題意了。舉個例子：
edge cost
1 <--> 2 2
1 <--> 3 2
1 <--> 4 1
2 <--> 3 3
然後讓 2 3 4 這三個節點相連通，所需要的最少 cost 應為 5。
※ 引述《tkcn (小安)》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 給定一個無向圖，edge都有cost。
: : 現在在圖上已選定了一些節點，我們想要把這些節點連接起來，讓它們兩兩都相連通。
: : 請問最少的cost為多少？
: : 這個問題跟minimum spanning tree的差別是，
: : minimum spanning tree需要串起圖上所有節點，
: : 而這個問題只需串起選定的節點即可。
: : 請問這個問題該如何解決？
: 找出所有被選定的點之間的最短路徑，
: 便可建出一個虛擬的 graph，而且是 complete graph，
: 找出 MST 再從虛擬的 edge 中找回對應的最短路徑。
: 實際寫演算法的話，
: 可以不用真的去產生那虛擬的 graph，
: 只要將原先的 MST 搭配 all-pairs shortest path 產生的表格即可。
: 有錯請指正。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.90.81
※ 編輯: DJWS 來自: 140.112.90.81 (12/23 12:54)