[理工] 104交大 演算法shortest path

作者: st945712 (st945712)   2018-11-28 22:24:23
http://i.imgur.com/0CBzmGb.jpg
我想問的是(a)選項,他說除了s之外的所有點v,都存在一個邊(u,v)使得
最短(s,v)=最短(s,u)+(u,v) //且(u,v)為正
我的疑惑是:那如果v是取離s最近的點,上面那個等式不就不會成立了嗎??
像是下圖~~
http://i.imgur.com/B4SX5gV.jpg
還是我誤會他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