Re: [問題] 一個圖論的問題
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間17年前 (2007/12/22 19:59)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/6 (看更多)
※ 引述《DJWS (...)》之銘言：
: 給定一個無向圖，edge都有cost。
: 現在在圖上已選定了一些節點，我們想要把這些節點連接起來，讓它們兩兩都相連通。
: 請問最少的cost為多少？
: 這個問題跟minimum spanning tree的差別是，
: minimum spanning tree需要串起圖上所有節點，
: 而這個問題只需串起選定的節點即可。
: 請問這個問題該如何解決？
找出所有被選定的點之間的最短路徑，
便可建出一個虛擬的 graph，而且是 complete graph，
找出 MST 再從虛擬的 edge 中找回對應的最短路徑。
實際寫演算法的話，
可以不用真的去產生那虛擬的 graph，
只要將原先的 MST 搭配 all-pairs shortest path 產生的表格即可。
有錯請指正。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.156.83
推
12/23 18:37, , 1F
12/23 18:37, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
