1.求下图中 v1到 v6的最短路

解：(1) P(v1)=0, v1标号(vs,0) (2) (v1,v2)(v1,v3)A， T(v2)=min[T(v2),P(v1)+w12]=min[+∞,0+6]=6 T(v3)=minT(v3),P(v1)+w13]=min[+∞,0+1]=1 T(v3)=1最小，令P(v3)=1，v3标号（v1,1） (3) (v3,v2) (v3,v4) (v3,v5)A， T(v2)=min[T(v2),P(v3)+w32]=min[6,1+2]=3 T(v4)=min[T(v4),P(v3)+w34]=min[+∞,1+6]=7 T(v5)=min[T(v5),P(v3)+w35]=min[+∞,1+10]=11 T(v2)=3最小令P(v2)=3，v2标号（v3,3） (4) (v2,v4)A T(v4)=min[T(v4),P(v2)+w24]=min[7,3+1]=4 T(v4)=4最小，令P(v4)=4，v4标号（v2,4） (5) (v4,v5) (v4,v6)A， T(v5)=min[T(v5),P(v4)+w45]=min[11,4+4]=8 T(v6)=min[T(v6),P(v4)+w46]=min[+∞,4+6]=10 T(v5)=8最小，令P(v5)=8，v5标号（v4,8） (6) (v5,v6)A， T(v6)=min[T(v6),P(v5)+w56]=min[10,8+4]=10 T(v6)=10最小，令P(v6)=10，v6标号（v4,10） v1-v6最短路为v1-v3-v2-v4-v6，路长10。