例题 最短路的号法.docx

例题 最短路的号法例题 最短路的标号法 例1 用Dijkstra标号法求vs到vt的最短路及最短路线 v2 6 vt 10 2 5 vs 5 12 v4 3 v3 解：i=0,给vs标上(P(vs)=0,l(vs)=0),其余各点均为T标号点，T(vj)=+¥,l(vj)=M,j=2,3,4,t，记S0=vs,k=s。 i=1,考察以vs为起点的弧的终点v2、v3，由于P(vs)+ws2=0+10=10<+¥、P(vs)+ws3=0+3=3<¥，修改v2、v3的T标号分别为T(v2)=10,l(v2)=s,T(v3)=3,l(v3)=s。计算minT(vj)=T(v3)，将v3的T标号改为P标号，即P(v3)=3,记S1=vs,v3,k=3. i=2,考察以v3为起点的弧的终点v2、v4，由于P(v3)+w32=3+5=8<10，P(v3)+w34=3+12=15<+¥，修改v2、v4的T标号分别为T(v2)=8,l(v2)=3,T(v4)=15,l(v4)=3。计算minT(vj)=T(v2)，将v2的T标号改为P标号，即P(v2)=8，记S2=vs,v3,v2,k=2. i=3,考察以v2为起点的弧的终点v4、vt，由于P(v2)+w2t=8+6=14<+¥，P(v2)+w24=8+2=10<15，修改vt、v4的T标号为T(vt)=14,l(vt)=2，T(vj)=T(v4)，将v4的T标号改为P标号，即T(v4)=10,l(v4)=2。计算minP(v4)=10，记S3=vs,v3,v2,v4,k=4. i=4,考察以v4为起点的弧的终点vt，由于P(v4)+w4t=10+3=13<14，修改vt的T(vj)=T(vt)，T标号为T(vt)=13,l(vt)=4，计算min将vt的T标号改为P标号，即P(vt)=13，记S4=vs,v3,v2,v4,vt,k=t。 由于vt得到了P标号，所以得到了vs到vt的最短路vs,v3,v2,v4,vt，最短路的权为P(vt)=13。