Re: [問題] 一個圖論的問題
看板Prob_Solve (計算數學 Problem Solving)作者xu3jp68 (信箱爆炸..XD)時間17年前 (2007/12/23 17:48)推噓0(0推 0噓 0→)留言0則, 0人參與討論串3/6 (看更多)
※ 引述《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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
