[理工] 107台大 資演 minimax path

看板Grad-ProbAsk作者 (怪人幹怪事)時間5年前 (2021/01/11 20:13), 5年前編輯推噓1(1推 0噓 4→)
留言5則, 1人參與, 5年前最新討論串1/1
https://imgur.com/T8kbefI
我可以理解由dijkstra修改relax function 能得到這題的結果 正確性也想得出來 但是一開始解題想到的是用同樣模板的Prim's algo以求MST 目前想不到怎麼推翻之前的想法= = 想請教一下有沒有反例會使得Prim是錯誤的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.219 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1610367211.A.73D.html ※ 編輯: aa871220 (140.113.136.219 臺灣), 01/11/2021 20:15:23 ※ 編輯: aa871220 (140.113.136.219 臺灣), 01/11/2021 20:17:11
推
01/12 14:35, 5年前 , 1F
我的理解是第一題是undirected graph
01/12 14:35, 1F
→
01/12 14:35, 5年前 , 2F
是可以用mst algorithm算出來而且答案同dijkstra
01/12 14:35, 2F
→
01/12 14:35, 5年前 , 3F
但第二題是directed graph就不能了 只能用dijkstra
01/12 14:35, 3F
→
01/12 14:36, 5年前 , 4F
01/12 14:36, 4F
→
01/12 14:36, 5年前 , 5F
m
01/12 14:36, 5F
‣ 更多 aa871220 的文章
文章代碼(AID): #1V_43hSz (Grad-ProbAsk)