[理工] 104交大 算法shortest path

楼主: st945712 (st945712)   2018-11-28 22:24:23


我想问的是(a)选项,他说除了s之外的所有点v,都存在一个边(u,v)使得
最短(s,v)=最短(s,u)+(u,v) //且(u,v)为正
我的疑惑是:那如果v是取离s最近的点,上面那个等式不就不会成立了吗??
像是下图~~


还是我误会他a选项的意思了?
作者: f255577 (沈大妈)   2018-11-28 22:41:00
试看看u=s,等号右边的最小距离=0
楼主: st945712 (st945712)   2018-11-28 23:25:00
感谢f大0.0 我忘记题目没规定u不能等于s...

Links booklink

Contact Us: admin [ a t ] ucptt.com