T(V6=5 (e)P(v1)=0,P(v2)=1 P(V3)=3P(V4)=4 P(V6= (图10) 此时仍有T标号点ⅴs不能改为P标号,说明不存在从v到ⅴ的路, 所以计算终止。图e)中各方框的数字表示从v到各点的最短路长 D氏标号法只适用于全部权为非负情况。如果网络中含有负权的弧 则算法失效,应改用其它算法。 二、求网络中任意两点意最短路的 Floyd算法 对求网络中任意两点间的最短路,当然可用改变起始点的办法,采用 D氏标号法达到目的,但显然较繁。 Floyd算法却可直接求出网络中任意两 点间的最短路,且w的正负不受限制。 Floyd方法的具体步骤如下 开始(k=0),作距离矩阵Lo=(L)和序号矩阵0=(0n4) 其中, v;)∈ (LJF=1,2,…p) 第一步:k=r(1≤rsp)时,L()中第k行和第k列元素保持不变,其它元 素按下式计算,并填入L=()中30 T(v6)=5 T(v6)5 v2 v5 v1 v3 v6 (e) P(v1)=0,P(v2)=1 P(v3)=3,P(v4)=4 P(v6)=5 （图 10） 此时仍有 T 标号点 v5 不能改为 P 标号，说明不存在从 v1 到 v5 的路， 所以计算终止。图(e)中各方框的数字表示从 v1 到各点的最短路长。 D 氏标号法只适用于全部权为非负情况。如果网络中含有负权的弧， 则算法失效，应改用其它算法。 二、求网络中任意两点意最短路的 Floyd 算法 对求网络中任意两点间的最短路，当然可用改变起始点的办法，采用 D 氏标号法达到目的，但显然较繁。Floyd 算法却可直接求出网络中任意两 点间的最短路，且 wij 的正负不受限制。 Floyd 方法的具体步骤如下： 开始(k=0)，作距离矩阵 L (o)=(Lij(o))和序号矩阵 (o)=(ij(o)) 其中，    +   = v v A L o ij i j ij ( , ) ( )  ij(o)=j (i,j=1,2,…p) 第一步：k=r(1rp)时，L (k)中第 k 行和第 k 列元素保持不变，其它元 素按下式计算，并填入 L (k)=(Lij(k))中：