[理工] 107台大 資演 minimax path

[aa871220 (怪人幹怪事)]

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
推 jason35512: 我的理解是第一題是undirected graph
→ jason35512: 是可以用mst algorithm算出來而且答案同dijkstra
→ jason35512: 但第二題是directed graph就不能了 只能用dijkstra
→ jason35512: https://en.m.wikipedia.org/wiki/Widest_path_proble
→ jason35512: m
推 nofucknolove: mst只能保證整棵樹最小，但不能保證va->vb最小。
→ nofucknolove: 所以不能用mst吧