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

看板Grad-ProbAsk作者 (andrew)時間6年前 (2019/07/04 08:56), 編輯推噓0(0推 0噓 10→)
留言10則, 2人參與, 6年前最新討論串1/1
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
→
07/04 13:04, 6年前 , 1F
這題和MST有啥關係？
07/04 13:04, 1F
→
07/04 13:05, 6年前 , 2F
題目一開始不就說是有向無環圖了？
07/04 13:05, 2F
→
07/04 13:06, 6年前 , 3F
MST的定義是給定一個graph
07/04 13:06, 3F
→
07/04 13:07, 6年前 , 4F
找到讓所有點"互通" 並且使cost最小
07/04 13:07, 4F
→
07/04 13:07, 6年前 , 5F
"有向圖" 不會 "互通"，你對於定義好像沒弄得很清楚
07/04 13:07, 5F
→
07/04 13:09, 6年前 , 6F
這題要找以capital為source的SSSP才對
07/04 13:09, 6F
→
07/04 13:11, 6年前 , 7F
SSSP每次找出值最小的node去更新其他node的值
07/04 13:11, 7F
→
07/04 13:12, 6年前 , 8F
所以保證每個node都會是最小的 (optimal)
07/04 13:12, 8F
→
07/04 13:12, 6年前 , 9F
不曉得這樣有沒有解釋到你的問題？
07/04 13:12, 9F
→
07/04 13:42, 6年前 , 10F
謝謝解釋，我懂了！
07/04 13:42, 10F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1T7Kwyqv (Grad-ProbAsk)