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

楼主: ff00662299 (goneboy)   2020-07-16 18:40:27
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)吧?
作者: chengweihsu (安安你好)   2020-07-16 19:46:00
u.d原本已经加上在u的游玩时间了,你看一开始s.d就已经是c(v1)了所以relax v.d时,v.d = min {v.d, (u.d+uv距离+在v玩的时间)}

Links booklink

Contact Us: admin [ a t ] ucptt.com