[理工] 演算法-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