Re: [理工] [資結]-MST和shortest path

看板Grad-ProbAsk作者 (Ace)時間15年前 (2010/03/18 17:54), 編輯推噓2(2推 0噓 0→)
留言2則, 2人參與, 最新討論串2/2 (看更多)
※ 引述《EntHeEnd (...)》之銘言： : 請問這兩者不一定相等要怎樣証明呢 ? : 直接說因為有cycle時 可能就沒辦法選較小的邊的反例嗎 : 如 : 1 1 : a---b---c : \ / : 2 \ / 1 : \ / : d : 這樣{a,d}在MST不會選到 可是 在最短路徑要選這樣嗎 1 a ------- b | | |1 |1 | | c-------- d 1 則MST可以為abdc，而MST中ac最短路徑為3，但ac之實際短路徑為1 不知道你是否問這個~ ※ 編輯: assassin88 來自: 61.57.78.223 (03/18 17:55)
推
03/18 17:56, , 1F
恩 就是這個
03/18 17:56, 1F
推
03/18 18:51, , 2F
交大考題
03/18 18:51, 2F
‣ 更多 assassin88 的文章
文章代碼(AID): #1BeVXHeE (Grad-ProbAsk)
‣ 更多 assassin88 的文章
文章代碼(AID): #1BeVXHeE (Grad-ProbAsk)