[理工] 演算法187（106台大）！ Aa841018 PTT批踢踢實業坊

[理工] 演算法187（106台大）！

作者: Aa841018 (andrew) 2019-07-04 08:56:26

https://i.imgur.com/AcOhtV8.jpg
https://i.imgur.com/0vaD1Hl.jpg
https://i.imgur.com/yJuU2Kl.jpg
想請教一下，為何將G的點、邊看過就可得出是optimal?
證optimal不是應該利用矛盾證法確定找不出更小的MST才是嗎？

作者: mathtsai (mathtsai) 2019-07-04 13:04:00

這題和MST有啥關係？題目一開始不就說是有向無環圖了？MST的定義是給定一個graph找到讓所有點"互通" 並且使cost最小"有向圖" 不會 "互通"，你對於定義好像沒弄得很清楚這題要找以capital為source的SSSP才對SSSP每次找出值最小的node去更新其他node的值所以保證每個node都會是最小的 (optimal)不曉得這樣有沒有解釋到你的問題？

作者: Aa841018 (andrew) 2019-07-04 13:42:00

謝謝解釋，我懂了！

繼續閱讀

線代 4-126 範例三houallan5478 [理工] 線代內積空間shinle14 [理工] 資料結構p35第5題david95525 [理工] 線代8-59_範例3fmtshk Re: 線代3-30Honor1984 線代3-30zxc2179vbnm 離散遞迴排組Yueh711 離散關於循環群AdonisLam 線代證明RS（AB)=RS(B)是要加什麼條件zxc2179vbnm Re: [理工] 資料結構 circular Queue問題kyuudonut