作者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/cn.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