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

[Aa841018 (andrew)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.1.203 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1562201788.A.D39.html
→ mathtsai: 這題和MST有啥關係？
→ mathtsai: 題目一開始不就說是有向無環圖了？
→ mathtsai: MST的定義是給定一個graph
→ mathtsai: 找到讓所有點"互通" 並且使cost最小
→ mathtsai: "有向圖" 不會 "互通"，你對於定義好像沒弄得很清楚
→ mathtsai: 這題要找以capital為source的SSSP才對
→ mathtsai: SSSP每次找出值最小的node去更新其他node的值
→ mathtsai: 所以保證每個node都會是最小的 (optimal)
→ mathtsai: 不曉得這樣有沒有解釋到你的問題？
→ Aa841018: 謝謝解釋，我懂了！