作者st945712 (st945712)
看板Grad-ProbAsk
標題[理工] 104交大 演算法shortest path
時間Wed Nov 28 22:24:23 2018
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選項的意思了？
-----
Sent from JPTT on my Samsung SM-G950F.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.217.196
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1543415066.A.4BE.html
1F：推 f255577: 試看看u=s，等號右邊的最小距離=0 11/28 22:41
2F：→ st945712: 感謝f大0.0 我忘記題目沒規定u不能等於s... 11/28 23:25