推 EntHeEnd:恩 就是這個 03/18 17:56
推 ie925155:交大考題 03/18 18:51
※ 引述《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)