→ polomoss:謝謝 02/20 20:02
※ 引述《polomoss (小澤)》之銘言：
: : (2)
: : a.
: : 在G中 假設有條路徑 p(u,v),由u經過x1,x2,...,xn到v
: : 則p(w,x)=L(u,x1)+L(x2,x3)+...+L(xn,v) ...(1)
: : 已知在G'中 L'(w,x)=L(w,x)+s(w)-s(x)
: : L(w,x)=L'(w,x)-s(w)+s(x)
: : 代入(1)得
: : p(u,v)=L'(w,x1)+L'(x2,x3)+...+L'(xn,v)-s(u)+s(v)
: : 若假設G'中沿相同路徑稱為p'(u,v)，則
: : p'(u,v)=L'(u,x1)+L'(x2,x3)+...+L'(xn,v)
: : 則
: : p(u,v)=p'(u,v)-s(u)+s(v)
: : b.
: : 已知在G中w,x有最短路徑d(w,x)屬於p(w,x)
: : 且p(w,x)>=d(w,x) (註 大於或等於)
: : 由a知 G'中p(w,x)=p'(w,x)-s(w)+s(x)
: : 因此 p'(w,x)-s(w)+s(x) >= d'(w,x)-s(w)+s(x) (註 大於或等於)
: : p'(w,x)>= d'(w,x)
: : 由此知d'(w,x)為一最短路徑且與d(w,x)相同
: 第二題可以解釋題意嗎? 有點看不懂~不知道問什麼
假設現在每個點v上都有自己的一個值s(v)
現在有一個新的圖形G' 點集合和邊集合和G都一樣
但G'中 每一個邊上的length 是從G中的length導過來的
(u,v)在G'中的length = l(u,v) +s(u) - s(v)
上式中的l(u,v)是(u,v)這個邊在G上的length
請證明任兩點在G'中的shortest path
和在G中的shortest path會相同
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.79.115
※ 編輯: freetempo 來自: 61.57.79.115 (02/20 18:45)