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

[ff00662299 (Broken Coastline)]

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
→ chengweihsu: u.d原本已經加上在u的遊玩時間了，你看一開始s.d就
→ chengweihsu: 已經是c(v1)了
→ chengweihsu: 所以relax v.d時，
感謝！懂了，看來還是對演算法不夠細心
→ chengweihsu: v.d = min {v.d, (u.d+uv距離+在v玩的時間)}
※ 編輯: ff00662299 (49.216.65.159 臺灣), 07/16/2020 20:28:20