[理工] 演算法-DAG求Single-source-shortest pat

看板Grad-ProbAsk作者 (Broken Coastline)時間5年前 (2020/07/16 18:40), 5年前編輯推噓0(0推 0噓 4→)
留言4則, 1人參與, 5年前最新討論串1/1
https://i.imgur.com/Vhhoyjo.jpg
https://i.imgur.com/XJFwjht.jpg
想問54. Relax 為什麼是c(v) 不是c(u)？ 更新的話，如果要更新成經u到v, 不是應該加上在u點的遊玩時間，即c(u)嗎？ 而且比較的時候最終都會抵達v點，所以應該不會是加c(v)吧？ ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.65.159 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1594896029.A.6AC.html
→
07/16 19:46, 5年前 , 1F
u.d原本已經加上在u的遊玩時間了，你看一開始s.d就
07/16 19:46, 1F
→
07/16 19:46, 5年前 , 2F
已經是c(v1)了
07/16 19:46, 2F
→
07/16 19:54, 5年前 , 3F
所以relax v.d時，
07/16 19:54, 3F
感謝！懂了，看來還是對演算法不夠細心
→
07/16 19:54, 5年前 , 4F
v.d = min {v.d, (u.d+uv距離+在v玩的時間)}
07/16 19:54, 4F
※ 編輯: ff00662299 (49.216.65.159 臺灣), 07/16/2020 20:28:20
‣ 更多 ff00662299 的文章
文章代碼(AID): #1V42wTQi (Grad-ProbAsk)