[理工] 108交大資演 9

[leegaga61029 (粒粒)]

https://i.imgur.com/P8JGuQP.jpg

請問一下有人會這題嗎QQ
追好久還是寫錯


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.133.75 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580225960.A.3DA.html
推 mistel: 用臨接矩陣做Dijkstra's
→ mathtsai: 題目要問什麼
※ 編輯: leegaga61029 (101.12.133.75 臺灣), 01/29/2020 01:14:46
推 Justapig: 這一題trace的時候其實就是先從priority queue找最小，
→ Justapig: 然後再判斷哪些需要decrease key，不過如果沒有想到這個
→ Justapig: 直接追蹤也可以
→ Justapig: 題目我記得是問u_max最後的值
推 s42420808:  https://i.imgur.com/Fx7NDiy.jpg
→ s42420808: 剛剛做的供參字醜抱歉
→ mathtsai: 這題就是Dijkstra啊 只是他沒用priority queue來存
→ mathtsai: 目前距離最小的點而已
→ mathtsai: 他在找當前最小點的時候 花了O(V)來找而已