Li( k)=min Li(k-b), Lik k-l)+Lkj(k-l) (4.2) 相应地,0k)的各元素按下式变化: (k-1) 若L 若L0 (4.3) 第二步:若存在L<0(1≤ip),计算终止,即说明D中存在一条含有顶 点ⅵi的负回路Q,(即dn=W(Q)<O的回路),并由θ(i=1,2,…p,找出此 回路。否则,置k=k+1 第三步:当k→p,计算终止。若Lp=+∞,则说明D中不存在从ⅵ到 η的路;否则,记d=L,表示由ⅵ到v的最短路长,相应的最短路可由 OnP(j=1,2,…p)找出 例用 Floyd方法求图1l中各顶点间的最短路,其中弧(边)旁的数 字表示弧(边)长 (图11) 解:k=0,把图11中的两条边看作长度相等,方向相反的两条弧。即 有o14=041=9,o235=032=2。根据图11中的数据,作Lo=(L)同时作 00=(040),如表中k=0所示。 k=1,将L中第1行和第1列的元素保持不变(在表中用虚线将其覆 盖),其它元素按(42)式进行计算,例如 L42(=min{L42,L410+Ln2o}=min{∞,9+3}=12 L43(=min{L43o,L410+L3o}=min{∞,9+4}=13 其余元素经计算不变。对更新数字的元素均加上圆圈。 同时,在k=1的序数矩阵中,按(4.3)式有042=041=1,04=x=1,31 Lij(k)=min{Lij(k-1),Lik(k-1)+Lkj(k-1)} (4.2) 相应地， (k)的各元素按下式变化：      = = − − − − ( 1) ( ) ( 1) ( 1) ( ) ( 1) ( ) , , k ij k ij k ik k ij k ij k k ij ij L L L L 若 若    (4.3) 第二步：若存在 Lii<0(1ip)，计算终止，即说明 D 中存在一条含有顶 点 vi 的负回路 Q，(即 dii=W(Q)<0 的回路)，并由ij(k)(i,j=1,2,…p)，找出此 回路。否则，置 k=k+1。 第三步：当 k=p，计算终止。若 Lij(p)=+，则说明 D 中不存在从 vi 到 vj 的路；否则，记 dij=Lij(p)，表示由 vi 到 vj 的最短路长，相应的最短路可由 ij(p)(i,j=1,2,…p)找出。 例 用 Floyd 方法求图 11 中各顶点间的最短路，其中弧（边）旁的数 字表示弧（边）长。 （图 11） 解：k=0，把图 11 中的两条边看作长度相等，方向相反的两条弧。即 有14=41=9，25=52=2。根据图 11 中的数据，作 L (o)=(Lij(o))同时作  (0)=(ij(o))，如表中 k=0 所示。 k=1，将 L (1)中第 1 行和第 1 列的元素保持不变（在表中用虚线将其覆 盖），其它元素按(4.2)式进行计算，例如 L42(1)=min{L42(o),L41(o)+L12(o)}=min{,9+3}=12 L43(1)=min{L43(o),L41(o)+L13(o)}=min{,9+4}=13 其余元素经计算不变。对更新数字的元素均加上圆圈。 同时，在 k=1 的序数矩阵中，按(4.3)式有42(1)=41(o)=1，43(o)=41(o)=1， ° v2 v3 v5 v1 v4 -4 3 3 2 3 4 -1 9