【學習日記】Week 7 – 企業資料通訊 | 課後探討題目1| 兩個相鄰節點最小成本路徑

• 請考量下圖所示的部分網路。x 只有兩個相鄰節點w 跟y。w 前往目的端u (未顯示) 的最小成本路徑成本為5，y 前往u 的最小成本路徑成本為6。從w跟y 前往u (以及w跟y之間) 的完整路徑並未顯示在圖中。網路中所有連結的成本都是嚴格的正整數。[共60分，每題20分]

1. 請寫出x 針對目的端w、y、u 的距離向量。
2. 請提供c(x,w) 連結成本的改變，令x 在執行距離向量演算法時，會將其新的前往u 的最小成本路徑通知其相鄰節點。
3. 請提供c(x,y) 連結成本的改變，令x 在執行距離向量演算法時，不會將其新的前往u 的最小成本路徑通知其相鄰節點。

Answer:

a.
Dx(w)=min{c(x,w)+Dw(w) , c(x,y)+Dy(w)}= min {2+0 , 5+2}=2 Dx(y)=min{c(x,y)+Dy(y) , c(x,w)+Dw(y)}= min {5+0 , 2+2}=4
Dx(y)=min{c(x,y)+Dy(y) , c(x,w)+Dw(y)}= min {5+0 , 2+2}=4

b. if c(x,w)=50，Dx(u)=min{c(x,w)+c(w,u) , c(x,y)+c(y,u)}= min {50+5 , 5+6}=11

c. if c(x,y)=6，Dx(u)=min{c(x,w)+c(w,u) , c(x,y)+c(y,u)}= min {2+5 , 6+6}=7