[理工] 107台大資演 minimax path aa871220 PTT批踢踢實業坊

[理工] 107台大資演 minimax path

作者: aa871220 (TMVP_Yueko) 2021-01-11 20:13:29

https://imgur.com/T8kbefI
我可以理解由dijkstra修改relax function 能得到這題的結果
正確性也想得出來
但是一開始解題想到的是用同樣模板的Prim's algo以求MST
目前想不到怎麼推翻之前的想法= =
想請教一下有沒有反例會使得Prim是錯誤的

作者: jason35512 (jason2714) 2021-01-12 14:35:00

我的理解是第一題是undirected graph是可以用mst algorithm算出來而且答案同dijkstra但第二題是directed graph就不能了只能用dijkstrahttps://en.m.wikipedia.org/wiki/Widest_path_problem

繼續閱讀

[理工] 108中興數學bobo1004 [理工] 108中興資訊概論sososlee 109中興資工數學和演算法lucy35 [理工] 109中央演算法seafoodccu [理工] 計系成大 106 (2)try66889 [理工] 台大電機丙離散ThereisBear 109中興通訊 AM訊號IceHsuan [理工] 資演交大108 (10)(13)try66889 [理工] 106台聯大計組drosyo [理工] 93 中山電機計組smalldata

Contact Us: admin [ a t ] ucptt.com