作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] 演算法187（106台大）！
時間Thu Jul 4 08:56:26 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1562201788.A.D39.html
1F：→ mathtsai: 這題和MST有啥關係？ 07/04 13:04
2F：→ mathtsai: 題目一開始不就說是有向無環圖了？ 07/04 13:05
3F：→ mathtsai: MST的定義是給定一個graph 07/04 13:06
4F：→ mathtsai: 找到讓所有點"互通" 並且使cost最小 07/04 13:07
5F：→ mathtsai: "有向圖" 不會 "互通"，你對於定義好像沒弄得很清楚 07/04 13:07
6F：→ mathtsai: 這題要找以capital為source的SSSP才對 07/04 13:09
7F：→ mathtsai: SSSP每次找出值最小的node去更新其他node的值 07/04 13:11
8F：→ mathtsai: 所以保證每個node都會是最小的 (optimal) 07/04 13:12
9F：→ mathtsai: 不曉得這樣有沒有解釋到你的問題？ 07/04 13:12
10F：→ Aa841018: 謝謝解釋，我懂了！ 07/04 13:42