Re: [問題] 一個圖論的問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間17年前 (2007/12/23 12:54)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/6 (看更多)
你誤會題意了。舉個例子：
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)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
