作者ff00662299 (Broken Coastline)
看板Grad-ProbAsk
标题[理工] 演算法-DAG求Single-source-shortest pat
时间Thu Jul 16 18:40:27 2020
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1594896029.A.6AC.html
1F：→ chengweihsu: u.d原本已经加上在u的游玩时间了，你看一开始s.d就 07/16 19:46
2F：→ chengweihsu: 已经是c(v1)了 07/16 19:46
3F：→ chengweihsu: 所以relax v.d时， 07/16 19:54
感谢！懂了，看来还是对演算法不够细心
4F：→ chengweihsu: v.d = min {v.d, (u.d+uv距离+在v玩的时间)} 07/16 19:54
※ 编辑: ff00662299 (49.216.65.159 台湾), 07/16/2020 20:28:20