作者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/cn.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