step4:设刚获得永久性标号的点为k,对每个具有临时标 号的点j,计算 T()=min{(0),P(k)+bk; 对于T(j)发生了变化的每个结点j,令 PRIOR()=k然后 转Step3 教学建模
ä . ÚÊ . á´¯K9Ù{ 6¯K9Ù{ Step 4µf¼[È5IÒ: k§ézäkI Ò: j§O T(j) = min {T(j), P(k) + bkj} éu T(j) u) Czz(: j§- P RIOR(j) = k., = Step 3" Step 5µP(N) = 1 → N á´" P RIOR(ki) = ki−1, i = 1, 2, . . . , n; k0 = 1, kn = N Ká´»µ1 = k0 → k1 → k2 → · · · → kn = N. IEÆ êÆï
step4:设刚获得永久性标号的点为k,对每个具有临时标 号的点j,计算 T()=min{(0),P(k)+bk; 对于T(j)发生了变化的每个结点j,令 PRIOR()=k然后 转Step3 step5:P(N)即为1→N的最短路的长。 设 PRIOR(k1)=k2-1 1,2,,n;ko=1,k2=N 则最短路径为:1=k0→k1→k→…→kn=N 教学建模
ä . ÚÊ . á´¯K9Ù{ 6¯K9Ù{ Step 4µf¼[È5IÒ: k§ézäkI Ò: j§O T(j) = min {T(j), P(k) + bkj} éu T(j) u) Czz(: j§- P RIOR(j) = k., = Step 3" Step 5µP(N) = 1 → N á´" P RIOR(ki) = ki−1, i = 1, 2, . . . , n; k0 = 1, kn = N Ká´»µ1 = k0 → k1 → k2 → · · · → kn = N. IEÆ êÆï
回到例1 教学建模
ä . ÚÊ . á´¯K9Ù{ 6¯K9Ù{ £~ 1. P(1) = 0, T(j) = ∞, j = 2, 3, 4, 5, 6 T(2) = 0 + 16 = 16 T(3) = 0 + 22 = 22 T(4) = 0 + 30 = 30 T(5) = 0 + 41 = 41 T(6) = 0 + 59 = 59 P RIOR(j) = 1 j = 2, 3, 4, 5, 6 - P(2) = 16§=(: 2 [È5IÒ 16. IEÆ êÆï
回到例1. ①P(1)=0,T(j) j=2,3,4,5,6 T(2)=0+16=16T(3)=0+22=22 T(4)=0+30=30T(5)=0+41=41 T(6)=0+59=59 PRIOR(j)=1j=2,3,4,5,6 ③令P(2)=16,即给结点2永久性标号为16 教学建模
ä . ÚÊ . á´¯K9Ù{ 6¯K9Ù{ £~ 1. P(1) = 0, T(j) = ∞, j = 2, 3, 4, 5, 6 T(2) = 0 + 16 = 16 T(3) = 0 + 22 = 22 T(4) = 0 + 30 = 30 T(5) = 0 + 41 = 41 T(6) = 0 + 59 = 59 P RIOR(j) = 1 j = 2, 3, 4, 5, 6 - P(2) = 16§=(: 2 [È5IÒ 16. IEÆ êÆï
④T(3)=min{T(3),P(2)+b23}=min{2,16+16}=22 T(4)=min{(4),P(2)+b24}=min{30,16+22}=30 T(5)=min{(5),P(2)+b25}=min{41l,16+30}=41 r(6)=min{(6),P(2)+b6}=min{59,16+41}=57 只有结点6改变了临时标号,令PBⅠOB(6)=2 ⑤令P(3)=22,即给结点3永久性标号为22 教学建模
ä . ÚÊ . á´¯K9Ù{ 6¯K9Ù{ T(3) = min {T(3), P(2) + b23} = min {22, 16 + 16} = 22 T(4) = min {T(4), P(2) + b24} = min {30, 16 + 22} = 30 T(5) = min {T(5), P(2) + b25} = min {41, 16 + 30} = 41 T(6) = min {T(6), P(2) + b26} = min {59, 16 + 41} = 57 k(: 6 UC IÒ§- P RIOR(6) = 2. - P(3) = 22§=(: 3 [È5IÒ 22. IEÆ êÆï