PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 一個圖論的問題

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間17年前 (2007/12/23 20:12)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/6 (看更多)

謝謝你的回覆。 :) 如你所說，這個問題是給定一個圖，並選定一些節點，然後才要將這些節點兩兩都相連通。我對你提供的方法還有一些疑問。當選擇「成本最小的一條路徑」時，這是指最短路徑嗎？另外，如果「成本最小的一條路徑」不只一條時，該選擇哪一條路徑呢？我再舉個例子： edge cost 1 <--> 4 2 2 <--> 4 2 3 <--> 4 100 1 <--> 5 3 2 <--> 5 3 3 <--> 5 3 若要將 1 2 3 相連通，最少的 cost 為 9。依照你的演算法，如果先選擇了 1-4-2 這一條路徑，再選擇 1-5-3 這一條路徑，答案便會是10。（1-4-2是所有選定的點之間，最短的一條路徑。　1-5-3則是第二短的路徑當中字典順序最小的。） ※ 引述《xu3jp68 (信箱爆炸..XD)》之銘言： : ※ 引述《DJWS (...)》之銘言： : : 你誤會題意了。舉個例子： : : edge cost : : 1 <--> 2 2 : : 1 <--> 3 2 : : 1 <--> 4 1 : : 2 <--> 3 3 : : 然後讓 2 3 4 這三個節點相連通，所需要的最少 cost 應為 5。 : 假設你要找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.112.90.81 ※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:15) ※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:19) ※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:23) ※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:27)