7求图7.58 各图从儿到各点的最短路.docx

7求图7.58 各图从儿到各点的最短路..docx.(a)34Vl!(b)解:(a)i=0:So=山},P(v.)=0,2(片)=0,八匕•)=+oo,2(u)=M(i=2,3……11)k=l(V,,V2)€A,V2电So,p(V[)+W]2<八>2),故T(>2)修改为P(儿)+W[2=22(v2)修改为1(儿,v4)eA,v4e50,PW|)+W[4V卩0|4),故卩(y)修改为POJ+Wgug久心)修改为1min{T(v2),T(v4)}=T(v2)=2,令戸佃)=Hv2)=2,S)=S()U{v2}={v19v4,v2}k=2z=l(v2,v5)gA,v5gSpP(v2)+w25<r(v5),故T(v5)修改为P(v2)+w25=32(叩修改为2,(v2,v4)gA,v4^51,P(v2)+w24=T(v4)=8min{T(v4),T(v5)}=T(v5)=3,^P(v5)=3,S2={vrv2,v5},/:=5i=2:(v5,v4)gA,v4g52,P(v5)+vt^54=77>4)=&(W9)wi=2(v5,v4)gA,v4S2,P(v5)+w54=T(v4)=8,(v5,v9)gA,v9eS2),P(v5)+w59<T(v9),故T(v9)修改为4,2(v9)修改为5。0min{T(v4),T(v9)}=T(v9)=4,令P(Q=4鸟={片宀必“}*=9,z=3:修改T(yJ为P(v8)+vv98=11,修改2(v8)=9,修改T(v6)=P(v9)+w96=10,修改A(v6)=9min{T(v4),T(v8),T(v6)}=T(v4)=&令P(v6)=10,S4={^^2^5^9^4},/:=4z=4"Q修改为P(v4)+w43=15,2(*3)修改为4min{T(v=),T(v6),T(v3)}=T(v6)=10,令P(v6)=10,2(v6)=9;S5={vpv2,v5,v9,v4,%},k=6i=5T(v7)修改为P(v6)+vv67=14,2(v7)修改为6min{T(v8),T(v3),T(v7)}=T(v8)=ll令P(V8)=11,S6={片,”2,"5,"9*4*6,叫}北=8z=6T(vm)修改为P(v8)+w&H=20,2(vh)修改为8min{T(v3),T(v7),r(vI1)}=T(v7)=14P(v7)=14,/l(v7)=6,S7={vpv2,v3,v9,v4,v6,v8,v7},k=lz=7T(v10)W改为15,A(v10)修改为7,令min{T(v3),r(v11),r(v10)}=T(v3)=T(vl0)=I5令P(V3)=15,P%)=15,2(%)=7,S8={儿*2*5*9“,%,%卩宀,%*=10z=8对已经标号V3,(V3,v7)WS,但V7已经标号。对己经标号Vi],有(v10,vn)WS,则T(V]])修改为P(V]O)+W1O.]1=15+4=19,x(vn)=10,所以P(Vn)=19,S9={V1,V2,V5,V9,V4,V6,V8,V7,V3,V1(),V11)d(vi,v2)=2,最短路为(V],v2);d(vbv5)=3,最短路为(V|,V2,V5);d(vbv9)=4,最短路为(V],V2,V5,V9);d(V],V7)=14,最短路为(VI,V2,V5,V9,V6,V7);d(V