(3)比较所有具有T标号点,把最小者改为P标号,即 P(vjo=min T(vi) 为T标号 若全部点均为P标号。则停止。否则以v代v,返回(2) 例,用 Dijkstra标号法求下图由v到各顶点的最短路。 (图9) 解:标号过程如图10中(a)-(e),其中方框表示P标号,里面的数字 表示从v到该点的最短路长。圆圈表示T标号,其中的数字表示从v到该 点最短路长的上界 (a)P(v1)=0,T(v2)=1 (b)P(v)=0,P(v2)1 T(v3)=4 T(v3)=3,T(4)=4 (c)P(v1)=0,T(v2)=1 (dP(vl)=0,P(v2)=1 P(V3)=3,T(V4)=4 P(v3)=3,P(29 (3)比较所有具有 T 标号点，把最小者改为 P 标号，即 P(vjo)=min{T(vj)} vj 为 T 标号 若全部点均为 P 标号。则停止。否则以 vjo 代 vi，返回(2) 例，用 Dijkstra 标号法求下图由 v1 到各顶点的最短路。 v2 v5 v1 v3 v6 （图 9） 解：标号过程如图 10 中(a)－(e)，其中方框表示 P 标号，里面的数字 表示从 v1 到该点的最短路长。圆圈表示 T 标号，其中的数字表示从 v1 到该 点最短路长的上界。 v2 + v2 + v1 v1 v3 + v3 + (a) P(v1)=0,T(v2)=1 (b)P(v1)=0,P(v2)=1 T(v3)=4 T(v3)=3,T(v4)=4 v2 + v2 + v1 v1 v3 v6 v3 v6 (c) P(v1)=0,T(v2)=1 (d)P(v1)=0,P(v2)=1 P(v3)=3,T(v4)=4 P(v3)=3,P(v4)=4 ° ° ° ° ° ° 2 3 3 2 1 1 1 2 4 2