※ 引述《DJWS (...)》之銘言： : 你誤會題意了。舉個例子： : edge cost : 1 <--> 2 2 : 1 <--> 3 2 : 1 <--> 4 1 : 2 <--> 3 3 : 然後讓 2 3 4 這三個節點相連通，所需要的最少 cost 應為 5。 : ※ 引述《tkcn (小安)》之銘言： : : 找出所有被選定的點之間的最短路徑， : : 便可建出一個虛擬的 graph，而且是 complete graph， : : 找出 MST 再從虛擬的 edge 中找回對應的最短路徑。 : : 實際寫演算法的話， : : 可以不用真的去產生那虛擬的 graph， : : 只要將原先的 MST 搭配 all-pairs shortest path 產生的表格即可。 : : 有錯請指正。 假設你要找2,3,4之間最小成本，所以找所有路徑當中跟2,3,4有關的， 選成本最小的一條，這邊是1 <--> 4，所以你現在收集了1跟4的點， 然後在搜尋有跟1,4當中有關的最小成本，這邊是1 <--> 2 or 1 <--> 3 假設你選1 <--> 2，所以你現在手上有1,2,4三個點，然後再搜尋 跟1,2,4有關的路徑當中成本最小的，最後得到1 <--> 3，總成本是5 所以我覺得應該是一開始你要先輸入你需要哪先點相連，輸入完再讓它 搜尋跟這些點有關係當中成本最小的路徑，所以每次搜尋應該就會連起來 一個你想要的點。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.53.85